// polyya定理 题意就是n种颜色n个球 求不同染色方案 "不考虑翻转"
//首先 n^gcd(n,i) i=0~n-1
// n太大 求 k=gcd（n,i）的个数 枚举q|n 1~sqrt(n) 再求phi(n/q) phi(q)
//
#include <iostream> #include <stdio.h> using namespace std; int Pow(int a,int b,int m) { int t; a=a%m; for(t=1;b;b>>=1) { if(b&1) t=(t*a)%m; a=(a*a)%m; } return t; } int phi(int n) { int i; int m=n; for(i=2;i*i<=n;i++) if(n%i==0){ m=m/i*(i-1); while(n%i==0) n/=i; } if(n!=1) m=m/n*(n-1); return m; } int main() { int X; int n,p; int i,ans; scanf("%d",&X); while(X--) { scanf("%d %d",&n,&p); ans=0; for(i=1;i*i<n;i++) { if(n%i==0) { ans+=(phi(n/i)%p)*Pow(n,i-1,p)%p; ans+=(phi(i)%p)*Pow(n,n/i-1,p)%p; ans%=p; } } if(i*i==n) ans+=(phi(n/i)%p)*Pow(n,i-1,p)%p; printf("%d\n",ans%p); } return 0; }
//稍微快一点
#include <iostream> #include <stdio.h> using namespace std; #define LL long long #define N 50000 int su[N/3],pn; bool use[N]; void sushu()//欧拉筛选素数法 { pn=0; for(int i=2;i<N;i++) { if(!use[i]) su[pn++]=i; for(int j=0;j<pn;j++) { if(su[j]*i>=N) break;//开始写 > 超时 改成>=就过了 想想只是一位的非法访问呀、真是细节 use[su[j]*i]=true; if(i%su[j]==0) break; } } } int Pow(int a,int b,int m) { int t; a=a%m; for(t=1;b;b>>=1) { if(b&1) t=(t*a)%m; a=(a*a)%m; } return t; } int phi(int n) { int i; int m=n; for(i=0;i<pn&&su[i]*su[i]<=n;i++) if(m%su[i]==0) { m-=m/su[i]; do{ n/=su[i]; }while(n%su[i]==0); } if(n!=1) m-=m/n; return m; } int main() { sushu(); int X; int n,p; int i,ans; scanf("%d",&X); while(X--) { scanf("%d %d",&n,&p); ans=0; for(i=1;i*i<n;i++) { if(n%i==0) { ans+=(phi(n/i)%p)*Pow(n,i-1,p)%p; ans+=(phi(i)%p)*Pow(n,n/i-1,p)%p; ans%=p; } } if(i*i==n) ans+=(phi(n/i)%p)*Pow(n,i-1,p)%p; printf("%d\n",ans%p); } return 0; }
原文：http://www.cnblogs.com/372465774y/p/3631066.html