Calculate
for large values of B, P, and M using an efficient algorithm. (That's right, this problem has a time dependency !!!.)
Input
Three integer values (in the order B, P, M) will be read one number per line. B and P are integers in the range 0 to 2147483647 inclusive. M is an integer in the range 1 to 46340 inclusive.
Output
The result of the computation. A single integer.
Sample Input
3 18132 17 17 1765 3 2374859 3029382 36123
Sample Output
13 2 13195 /* */ #include <stdio.h> #include <memory> int main ( ) { int a,b,n; while ( scanf ( "%d%d%d",&a,&b,&n )!= EOF ) { bool b2 [ 35 ]; memset (b2, 0, sizeof (b2 ) ); int tmp=b,i,d= 1; for ( i= 0; tmp> 0 ; i++ ) { b2 [i ]=tmp% 2; tmp=tmp/ 2; } for (;i>= 0;i-- ) { d=d*d%n; int aa=a%n; if ( b2 [i ]== 1 ) d=d*aa%n; } printf ( "%d/n",d ); } return 0; }
方法二：超短代码
#include <cstdio>int b, p, m, k;int main(){ while(scanf("%d%d%d", &b, &p, &m)!=EOF) { for(k=1,b=b%m; p ; p/=2,b=b*b%m) if(p%2) k=k*b%m; printf("%d\n", k%m); } return 0;}
方法三：递归 时间稍慢
#include <cstdio>int m;int bigmod(int a,int b){ if(!b)return 1; int d=bigmod(a,b>>1)%m; return b&1?(d*d%m*a)%m:(d*d)%m;}int main (){ int a,b; while (scanf("%d%d%d",&a,&b,&m)!=EOF) { int ans=bigmod(a%m,b)%m; printf("%d\n",ans); } return 0;}
快速幂取模 最短代码 for(k=1,a=a%m; b ; b>>=1,a=a*a%m) if(b&1) k=k*a%m; 求a^b(mod m) k%m是答案。
