题目地址：http://poj.org/problem?id=2154
一直WA，然后发现[n^n%p]/n与n^(n-1)%p不一样...
#include<iostream> #include<cstdio> #include<cmath> using namespace std; typedef long long LL; int N,P; int euler_phi(int n) { int res=1; for(int i=2;i*i<=n;i++) if(n%i==0) { //说明i|n n/=i,res*=i-1; while(n%i==0) n/=i,res*=i; //说明i^2|n } if(n>1) res*=n-1; return res%P; } LL PowMod(LL x,LL n,LL p) //x^n 对Max取模 { LL result=1; LL base = x%p; while(n>0) { if(n & 1) result=(result*base)%p; //当二进制不为0时，就要乘个 base=(base*base)%p; //累乘此时二进制的权值 n>>=1; } return result%p; } LL polya(int m,int n) //m color ,n number { LL tot=0; //方案数 for(int i=1;i*i<=n;i++) //1~sqrt(n) { if(n%i) continue; //当i不是n的约数时就进入下一次循环 tot+=euler_phi(i)*PowMod(m,n/i-1,P)/n; //本来是(pow(m,n/i)/n)%P 所以直接改为pow(m,n/i-1)%P,注意不能(pow(m,n/i)%P)/2 tot%=P; if(i*i!=n) tot+=euler_phi(n/i)*PowMod(m,i-1-1,P)/n; tot%=P; } return tot; } int main() { int T; cin>>T; while(T--) { cin>>N>>P; cout<<polya(N,N)<<endl; } return 0; }