学步园

/************************************************************************/<br /> | 求 a^n % b (a,b,n <= 1000000000) k is Z<br /> | 思路: a^n -> a^[ phi(b)*k + n%phi(b) ]根据欧拉定理 a^phi(b) % b ==1<br /> | 因此可先求 b 的欧拉函数 a^(phi(b)*k)%b=1 原式变成求 a^n%phi(b) mod b<br /> /************************************************************************/<br /> #include<iostream><br /> #include<cmath><br /> using namespace std;<br /> //求phi(x)<br /> int euler(int x)<br /> {<br /> int ret = x;<br /> for(int i=2; i<(int)(sqrt(1.00*x)+1); i++)<br /> {<br /> if(x%i==0)<br /> {<br /> ret = ret/i*(i-1);//公式<br /> while(x%i==0) x /= i;//保证i一定是不同素数<br /> }<br /> }<br /> if(x > 1) ret = ret/x*(x-1);<br /> return ret;<br /> }<br /> //计算a^n mod b b进制的最后一位<br /> int solve(int a, int n, int b)<br /> {<br /> int phi = euler(b);<br /> int m = n%phi;<br /> int ret = 1;<br /> for(int i=1; i<=m; i++)<br /> {<br /> ret *= a;<br /> ret %= b;<br /> }<br /> return ret;<br /> }<br /> int main()<br /> {<br /> int a, n, b;<br /> while(scanf("%d%d%d", &a, &n, &b)!=EOF)<br /> {<br /> if(a==0) break;<br /> int ret = solve(a, n, b);<br /> printf("%d/n", ret);<br /> }<br /> return 0;<br /> }