本文共 1607 字，大约阅读时间需要 5 分钟。
题意：中文题自己看吧
分析：这题分两步
第一步：利用已知公式求出k；
第二步：求出k然后使用欧拉降幂公式即可，欧拉降幂公式不需要互质（第二步就是BZOJ3884原题了）
求k的话就需要构造了（引入官方题解）
然后就求出k了，我就很奇怪为什么是这个式子，然后就网上搜啊搜
找到了一个推导（看完了以后恍然大悟）
推导链接：http://blog.csdn.net/wust_zzwh/article/details/51966450
高度仰慕数学好的巨巨
吐槽：这个题n是无平方因子，然后就要往欧拉函数是积性函数的性质上想，但是主要是还是要多做数学题
#include #include #include #include #include #include #include #include using namespace std;typedef long long LL;const int N = 1e7+5;const int mod=1e9+7;bool check[N];LL phi[N],prime[N>>1],tot;LL sum[N],k,n,m,p;LL qpow(LL a,LL b,LL mod){ LL ret=1; while(b){ if(b&1)ret=(ret*a)%mod; a=(a*a)%mod; b>>=1; } return ret;}void getphi(){ phi[1]=1;tot=0; for(int i=2;i<=N-5;++i){ if(!check[i]){ prime[++tot]=i; phi[i]=i-1; } for(int j=1;j<=tot;++j){ if(i*prime[j]>N-5)break; check[i*prime[j]]=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); } } for(int i=1;i<=N-5;++i){ sum[i]=(sum[i-1]+phi[i])%mod; }}LL solve(LL n,LL m){ if(m==0)return 0; if(m==1)return phi[n]; if(n==1)return sum[m]; if(phi[n]==n-1){ return (phi[n]*solve(1,m)%mod+solve(n,m/n))%mod; } for(int i=1;i<=tot&&prime[i]*prime[i]<=n;++i){ if(n%prime[i])continue; return (phi[prime[i]]*solve(n/prime[i],m)%mod+solve(n,m/prime[i]))%mod; }}LL f(LL x){ if(x==1)return 0; return qpow(k,f(phi[x])+phi[x],x);}int main(){ getphi(); while(~scanf("%I64d%I64d%I64d",&n,&m,&p)){ k=solve(n,m); printf("%I64d\n",f(p)); } return 0;}
转载于:https://www.cnblogs.com/shuguangzw/p/5698158.html
