快速求
a
b
a^b
ab
- 如果将a自乘一次，就会变成
a
2
a^2
a2。再把a
2
a^2
a2自乘一次就会变成a
4
a^4
a4，然后是a
8
a^8
a8……自乘n次的结果是a
2
n
a^{2^n}
a2n a
x
a^x
axa
y
a^y
ay=a
x
+
y
a^{x+y}
ax+y
int quickPower(int a, int b)//是求a的b次方{ int ans = 1, base = a;//ans为答案，base为a^(2^n) while(b > 0)//b是一个变化的二进制数，如果还没有用完 { if(b & 1)//&是位运算，b&1表示b在二进制下最后一位是不是1，如果是： ans *= base;//把ans乘上对应的a^(2^n) base *= base;//base自乘，由a^(2^n)变成a^(2^(n+1)) b >>= 1;//位运算，b右移一位，如101变成10（把最右边的1移掉了），10010变成1001。现在b在二进制下最后一位是刚刚的倒数第二位。结合上面b & 1食用更佳 } return ans;}- 取余运算
(A + B) mod b = (A mod b + B mod b) mod b
(A × B) mod b = ((A mod b) × (B mod b)) mod b
while(b > 0) { if(b & 1) { ans *= base; ans %= m; /*ans=(ans*base)%K*/ } base *= base; base %= m; b >>= 1; }能保证这样下来最后的结果与“先乘到最后，再取余”的结果一样。
#include<cstdio>
#include<iostream>
using namespace std;
long long a,b,k;
long long ksm(long long a,long long b){
long long base=a,ans=1;
while(b>0){
if(b&1){
ans*=base;
ans%=k;
}
base*=base;
base%=k;
b>>=1;
}
return ans%k;
}
int main(){
cin>>a>>b>>k;
cout<<a<<"^"<<b<<" mod "<<k<<"="<<ksm(a,b);
return 0;
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/151011.html
