程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> FZU Super A^B mod C

FZU Super A^B mod C

編輯：C++入門知識

FZU Super A^B mod 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

*/