其主要利用的原理就是
a^4 % c=(a^2)^2 % c;
那么这样去快速地算明显是指数级别的计算速度 #include using namespace std; int main() { int a,b,c; while (scanf("%d%d%d",&a,&b,&c)!=EOF&&a!=0&&b!=0&&c!=0) { int k=1; while (b>0) { if(b%2==1) k=(k*a)%c;// 作用：当 b为奇数，则先单独乘一个 a=(a*a)%c; b = (b>>1); // a1=a%c 1=2^0 // a2=((a%c)*(a%c))%c 2=2^1 // a3=((a%c*a%c)%c*(a%c*a%c)%c) 4=2^2 //由此，可知 b=b/2 ,每次的 a 的个数为上一次的 2倍 //k在最后b==1的时候会把前面所有的b为偶数项的时候积攒下来的数一次性乘进去 } printf("%d ",k); } return 0; } 下面再给出简单形式的 int fastpow(int a,int b,int c){ int res=1; while(b){ if(b&1) res=(res*a)%c; a=(a*a)%c; b>>=1; } return res; } 但是如果a,b都是很大的话就要用long long，这里有一个小技巧：
根据费马小定理

如果c是一个素数，那么a^b%c==a^( b%(c-1) )%c

利用快速幂的思想还可以实现快速乘，其实就是把a*a变成了a*2而已 ll multiply(ll a,ll b){ ll res=0; while(b){ if (b&1) res=(res+a)%MOD; a=(a*2)%MOD; b>>=1; } return res; }