欧拉函数phic以及超大数的快速幂

题目：求a^b*c%mod;

其中b<=10^100000;

是不是很大.....

/*当你要计算 A^B%C的时候

因为此题中的B很大，达到10^100000，所以我们应该联想到降幂公式。

降幂公式：A^B%C = A^(B%phi(C) + phi(C))%C

分两种情况：

当B<=phi(C)时，直接用快速幂计算A^B mod C

当B>phi(C)时，用快速幂计算A^(B mod phi(C)+phi(C)) mod C

*/

#include <cstdio>

#include <cstring>

#include <cmath>

#include <iostream>

#include <algorithm>

#include <string>

#include <cstdlib>

using namespace std;

const int mod = 1e9+;

typedef long long ll;

ll phi(ll n)   //求欧拉函数值

{

    int ans=n,temp=n;

    for(int i=;i*i<=temp;i++)

    {

        if(temp%i==)

        {

            ans-=ans/i;

            while(temp%i== ) temp/=i;

        }

    }

    if(temp>) ans-=ans/temp;

    return ans;

}

ll mod_pow(ll x,ll n,ll mod)  //快速幂

{

    ll ans=;

    while(n)

    {

        if(n%==) ans=ans*x%mod;

        x=x*x%mod;

        n/=;

    }

    return ans;

}

ll a,c;

char b[];

int main()

{

    while(scanf("%lld%s%lld",&a,b,&c)!=EOF)

    {

        c%=mod;

        a%=mod;

        ll phic=phi(mod);

        int i,len=strlen(b);

        ll res=,ans;

        for( i=;i<len;i++)

        {

            res=res*+b[i]-'';

            if(res>phic)

            break;

        }

        if(i==len)

        {

            ans=mod_pow(a,res,mod)*c%mod;

        }

        else

        {

            res=;

            for(int i=;i<len;i++)

            {

                res=res*+b[i]-'';

                res%=phic;

            }

            ans=mod_pow(a,res+phic,mod)*c%mod;

        }

        cout<<ans<<endl;

    }

    //cout<<mod_pow(2,3,mod);

    return ;

}