FZU Super A^B mod C - c++编程基础

Super A^B mod C

Given A,B,C, You should quickly calculate the result of A^B mod C. (1<=A,C<=1000000000,1<=B<=10^1000000).

There are multiply testcases. Each testcase, there is one line contains three integers A, B and C, separated by a single space.

Output

For each testcase, output an integer, denotes the result of A^B mod C.

Sample Input

3 2 4 2 10 1000

Sample Output

1 24

算法分析：

欧拉函数值得一个应用。即：A^B % C = A^(B%(euler_phi(C)) % C * A ^ euler_phi(C)。

至于如何退出这个定理的话，我就不知道了。感兴趣的可以自己百度。而等式为什么成立呢〉？

因为，我们会发现一个规律。当A^B % C 的时候，会在某个数后出现循环节。而总结规律会发现，这个循环节刚好就是euler_phi(C)。所以，我们只要最B先取余欧拉值就会得使得数据变成在10^9以内，这时候就可以用普通的做法解决了。

而如果当C是素数的时候却是特殊的情况。由费马小定理我们可以知道，此时A^B % C = A ^ (B %(C - 1)) % C 用java写老是CE.......后来无奈的只能用暴力模拟了。

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
        #include 
        
          #include 
         
           #include 
          
            using namespace std; typedef long long LL; typedef pair
           
             P; inline int read(){ int x = 0,f = 1; char ch = getchar(); while(ch < '0'||ch > '9'){if(ch == '-')f=-1;ch = getchar();} while(ch >= '0'&&ch <= '9'){x = x * 10 + ch -'0';ch = getchar();} return x*f; } ////////////////////////////////////////////////////////////////// LL A,C; char B[1000005]; LL euler_phi(LL n){ int m = sqrt(n + 0.5); LL ans = n; for(int i = 2;i <= m;++i)if(0 == n % i){ ans = ans / i * (i-1); while(0 == n % i) n /= i; } if(n > 1) ans = ans / n * (n-1); return ans; } LL getMod(char *str,LL m){ LL res = 0; int len = strlen(str); for(int i = 0;i < len;){ while(res < C&&i < len){ res = res * 10 + (str[i] - '0'); ++i; } //cout << "res: " << res << endl; res %= m; } return res; } LL powMod(LL a,LL b,LL mod){ LL res = 1; a %= mod; while(b > 0){ if(b & 1) res = res * a % mod; a = a * a % mod; b >>= 1; } return res % mod; } int main() { while(~scanf("%lld%s%lld",&A,B,&C)){ LL phi = euler_phi(C); LL mod = getMod(B,phi); // cout <<"phi: " << phi << " " << mod << endl; // LL tmp1 = powMod(A,phi,C); // cout << "A: " << A << " C: " << C << endl; // LL tmp2 = powMod(A,mod,C); // cout << "tmp1: " << tmp1 << " tmp2: " << tmp2 << endl; printf("%lld\n",powMod(A,phi,C) * powMod(A,mod,C) % C); } return 0; } /* 3 2 4 2 10 1000 */