首页 > 其他分享 >二分【2】快速幂 单峰序列

二分【2】快速幂 单峰序列

时间:2024-06-14 23:57:56浏览次数:29  
标签:二分 return int ll 单峰 kuaisumi 序列 include lld

目录

快速幂

递归写法(a^b%m)

迭代写法 

 单峰序列


快速幂

a^n

n为奇数,转化为a*a^(n-1)

n为偶数,转化为计算b=a^(n/2),在计算b^2

a^b%m)

递归写法(a^b%m)

#include <iostream>
#include <vector>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
ll a,b,m;
ll kuaisumi(ll a,ll b,ll m)
{	 if(b==0) {return 1; }
	if(b%2==1) {return (a%m)*kuaisumi(a,b-1,m)%m;}//b奇数
	else
	{
		ll A=kuaisumi(a,b/2,m)%m;return A*A%m;
	 } 
	 //缺一个递归出口:

	
	 
}

int main()
{
	scanf("%lld %lld %lld",&a,&b,&m);
	printf("%lld",kuaisumi(a,b,m));
	
}
#include <iostream>
#include <vector>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
ll a,b,m;
ll kuaisumi(ll a,ll b,ll m)
{	 if(b==0) {return 1; }
	if(b%2==1) {return (a%m)*kuaisumi(a,b-1,m)%m;}//b奇数
	else
	{
		ll A=kuaisumi(a,b/2,m)%m;return A*A%m;
	 } 
	 //缺一个递归出口:

	
	 
}

int main()
{
	scanf("%lld %lld %lld",&a,&b,&m);
	printf("%lld",kuaisumi(a,b,m));
	
}

迭代写法 

#include <iostream>
#include <vector>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
ll a,b,m;

int main()
{
	scanf("%lld %lld %lld",&a,&b,&m);
	ll ans=1;
	while(b>0)
	{if(b&1) {ans=ans*a%m;b--;}
	else {b/=2;a=a*a%m;
	}
	 } 
	printf("%lld",ans);
	
}

 单峰序列

左增右减,找峰顶

#include <iostream>
#include <vector>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=100001;int n,num[N]; 
int bis(int a[],int left,int right)
{
while(left<right)
{
	int mid=left+(right-left)/2;
	if(a[mid]>a[mid-1])
	{
		if(a[mid]>a[mid+1]) return mid;
		else left=mid+1;
	}
	else right=mid-1;

}
return left;	
}


int main()
{
	scanf("%d",&n);for(int i=0;i<n;i++) scanf("%d",&num[i]);
	
	printf("%d",bis(num,0,n-1));
}

预告:二分【3】 旋转数组 

标签:二分,return,int,ll,单峰,kuaisumi,序列,include,lld
From: https://blog.csdn.net/m0_68339197/article/details/139663910

相关文章

  • 二分【3】 旋转数组
    目录旋转数组旋转数组找最小值旋转数组找指定值  严格递增序列递增序列 旋转序列找中位数: 旋转数组旋转数组找最小值思路#include<iostream>#include<vector>#include<cmath>#include<string>#include<cstring>#include<algorithm>usingnamespac......
  • CorelDRAW破解激活2024新版本序列号
    CorelDRAW破解2024最新版序列号激活码注册码,这可是个神奇的宝贝!......
  • 【Py/Java/C++三种语言OD独家2024D卷真题】20天拿下华为OD笔试之【二分查找】2024D-部
    有LeetCode算法/华为OD考试扣扣交流群可加948025485可上全网独家的欧弟OJ系统练习华子OD、大厂真题绿色聊天软件戳od1441了解算法冲刺训练(备注【CSDN】否则不通过)文章目录题目描述与示例题目描述输入描述输出描述示例输入输出说明解题思路代码pythonjavacpp时......
  • php反序列化个人笔记
    反序列化什么是反序列化?格式转换序列化:对象转换为字符串或者数组等格式反序列化:将数组或字符串转换成对象为什么会出现安全漏洞?魔术方法如何利用漏洞?通过构造pop链,找到代码的逻辑漏洞,进行getshell,rce等操作反序列化利用分为三类魔术方法的调用逻辑语言原生类的调用逻......
  • [强网杯 2019]Upload php反序列化代码审计
    进入页面发现有登录,随便注册一个用户登录试试。文件上传?传个试试,结果发现不论怎么上传都没用,还发现了cookie像是反序列化的东西。扫目录看看,发现源码。发现主要文件,做做审计吧。index.php<?phpnamespaceapp\web\controller;usethink\Controller;classIndexextend......
  • CSharpe中的IO+NPOI+序列化
    CSharpe中的IO+NPOI+序列化文件文件夹操作学习一下常见的文件、文件夹的操作。什么是IO流?I:就是inputO:就是output,故称:输入输出流将数据读入内存或者内存输出的过程。常见的IO流操作,一般说的是[内存]与[磁盘]之间的输入输出。作用持久化数据,保证数据不再丢失!文件操作......
  • 二叉搜索树序列
    题目链接二叉搜索树序列题目描述注意点二叉搜索树中的节点数在[0,1000]的范围内1<=节点值<=10^6解答思路本题的题目解释成一句话也就是:每一个节点都必须排在其子孙节点的前面,同一层的节点可以任意排列首先想到的是广度优先遍历,将每一层的节点加入到一个List......
  • 二分查找
    二分查找非递归intbsearchWithoutRecursion(inta[],intkey){intlow=0;inthigh=a.length-1;while(low<=high){intmid=low+(high-low)/2;if(a[mid]>key)high=mid-1;elseif(a[mid]......
  • (nice!!!)LeetCode 2813. 子序列最大优雅度(反悔贪心)
    2813.子序列最大优雅度思路:1.先对数组items按profit进行降序排序。2.把前k个最大的profit选中3.再遍历剩余的项目,看看能不能增加类别的数量。因为profit是递减的,所以只有类别的数量能增大的情况下,才考虑从选中的k个项目当中删掉重复的类别项目里面的最小profit。细节......
  • Python对象序列化库之dill使用详解
    概要在Python编程中,序列化(Serialization)和反序列化(Deserialization)是处理对象持久化和数据传输的常见任务。Python提供了内置的 pickle 模块用于对象序列化,但它在处理复杂对象(如带有lambda函数、生成器和闭包的对象)时存在一定局限性。dill 库是 pickle 的一个扩展......