POJ 2154 Color Polya定理+欧拉函数优化 -

题目地址：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|nn/=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;
}