HDU 5728 PowMod

主要的收获是学到了降幂公式（指数循环节？）(a^bpmod{n}=a^{bpmod{varphi(n)}+varphi(n)}pmod{n})，简证如下：
只要证明(a^{varphi(n)}=a^{2varphi(n)}pmod{n})

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define ms(arr,a) memset(arr,a,sizeof arr)
#define debug(x) cout<<"< "#x" = "<<x<<" >"<<endl
const int mod=1e9+7;
const int maxN=1e7+5;//
int prime[maxN],phi[maxN],sum[maxN];
bool mark[maxN];
void init_prime_phi()
{
    sum[1]=phi[1]=1;
    int cnt=0;
    for(int i=2;i<maxN;++i)
    {
        if(!mark[i]){prime[++cnt]=i;phi[i]=i-1;}
        for(int j=1;j<=cnt&&prime[j]*i<maxN;++j)
        {
            mark[prime[j]*i]=true;
            if(i%prime[j]==0){phi[i*prime[j]]=phi[i]*prime[j];break;}
            else phi[i*prime[j]]=phi[i]*(prime[j]-1);
        }
        sum[i]=(sum[i-1]+phi[i])%mod;
    }
}

int n,m,p;
int fac[20];int cnt;int times;
void init_fac(int x)
{
    cnt=0;
    for(int i=1;prime[i]<sqrt(x);++i)
        if(x%prime[i]==0){fac[++cnt]=prime[i];x/=prime[i];}
    if(x>1)fac[++cnt]=x;
}
int calc(int n,int m,int k)
{
    times++;
    if(m==0)return 0;
    if(n==1)return sum[m];
    return (1LL*phi[fac[k]]*calc(n/fac[k],m,k-1)%mod+calc(n,m/fac[k],k))%mod;
}
int quick_pow(int a,int n,int p)
{
    register int ret=1;
    while(n)
    {
        if(n&1)ret=1LL*ret*a%p;
        a=1LL*a*a%p;
        n>>=1;
    }
    return ret;
}
int inf_pow(int k,int p)
{
    if(p==1)return 1;
    return quick_pow(k,inf_pow(k,phi[p])+phi[p],p);
}
int main()
{
	//freopen("Input.txt","r",stdin);
	//freopen("1.txt","w",stdout);
    init_prime_phi();
    while(~scanf("%d%d%d",&n,&m,&p))
    {
        init_fac(n);
        printf("%d
",inf_pow(calc(n,m,cnt),p));
    }
	//freopen("CON","w",stdout);
	//system("start Output.txt");
}