快速幂取模

   咱们在计算a的n次方模m的结果,有很多种的方法这里有种log(n)的方法 在n比较大的时候还是比较合算的

#include<iostream> #include<cstdio> #include<string.h> using namespace std; __int64 pow_mod1(__int64 a,__int64 n,__int64 m) {if(n==0) return 1;__int64 ans,x=pow_mod1(a,n/2,m);ans=(x*x)%m;if(n%2) ans=(ans*a)%m;return ans; } __int64 pow_mod2(__int64 a, __int64 b, __int64 c) {__int64 ans = 1;a = a % c;while(b>0){if(b%2==1)ans = (ans * a) % c;b = b/2;a = (a * a) % c;}return ans; }int main() {__int64 a,n,m;while(scanf("%I64d%I64d%I64d",&a,&n,&m)==3){a=a%m;printf("%I64d\n",pow_mod1(a,n,m));printf("%I64d\n",pow_mod2(a,n,m));}return 0; }

 

转载于:https://www.cnblogs.com/Opaser/p/3662065.html

总结

以上是生活随笔为你收集整理的快速幂取模的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。