欧拉降幂公式 Super A^B mod C

Description

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

Input

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.

降幂公式:

//计算欧拉函数O(sqrt(n))
ll Phi(ll x)
{
        ll i;
        ll re = x;
        for (i = ; i * i <= x; i++)
                if (x % i == )
                {
                        re /= i;
                        re *= i - ;
                        while (x % i == )
                        {
                                x /= i;
                        }
                }
        if (x ^ )
        {
                re /= x, re *= x - ;
        }
        return re;
}
ll Quick_Power(ll x, ll y, ll p)
{
        ll re = ;
        while (y)
        {
                if (y & )
                {
                        (re *= x) %= p;
                }
                (x *= x) %= p;
                y >>= ;
        }
        return re;
}
int Solve(int p)
{
        if (p == )
        {
                return ;
        }
        int phi_p = Phi(p);
        return Quick_Power(, Solve(phi_p) + phi_p, p);
}
int T, n, a, c;
string b;
int main()
{
        ios_base::sync_with_stdio(false);
        //    freopen("data.txt","r",stdin);
        while (cin >> a >> b >> c)
        {
                int phi_c = Phi(c);
                ll sum = ;
                for (int i = ; i < b.size(); i++)
                {
                        sum = (sum *  + b[i] - '') % (phi_c);
                }
                cout << Quick_Power(a, sum + phi_c, c) << endl;
        }
}