一.快速幂模(不爆long long)
-
l
o
g
2
n
log_2n
log2?n求a的b次方模p 即abmod p
递归原理 ab=ab/2ab/2(a)
long long ksm(long long a,long long b){
if(b==1)return a;
long long t=ksm(a,b/2);
if(b%2)return t*t*a%p;
else return t*t%p;
}
递推原理 ab=(a*a)b/2(a)
long long ksm(long long a,long long b){
long long x=1;
while(b){
if(b%2)x=x*a%p;
a=a*a%p;
b/=2;
}
return x;
}
b过大怎么办
- 费马小定理说：
a
b
%
p
=
a
b
%
(
p
?
1
)
%
p
a^b\%p=a^{b\%(p-1)}\%p
ab%p=ab%(p?1)%p
二.慢速乘
- 对于求abmod p，若模数p较大且不超过long long，导致a2可能超过了long long的范围
- 那么如何求快速幂呢？？？
慢速乘！！！
- 时间复杂度为O(
l
o
g
2
b
log_2b
log2?b)
- 算法原理：二进制下的乘法
long long mul(long long a,long long b,long long p=1e9+7){
long long res=0;
while(b){
if(b%2)res=(res+a)%p;
a=(a+a)%p;
b/=2;
}
return res;
}
int main(){
long long a,b;
cin>>a>>b;
cout<<mul(a,b);
return 0;
}
cs
