题意:将正n边形的n个顶点用n种颜色染色,问有多少种方案(答案mod p,且可由旋转互相得到的算一种)
先说说Pólya定理
设Q是n个对象的一个置换群,用m种颜色涂染这n个对象,一个对象涂任意一种颜色,则在Q作用下不等价的方案数为:
|Q|为置换群中置换的个数,为将置换q表示成不相杂的轮换的个数,其中包括单轮换,m为颜色数。
分析可以知道本题方案的表达式为:
然后就直接代码了:
#include <stdio.h> #include <string.h> #define N 36000 int p; int pr[N]; bool prime[N]; int k=0; void isprime() { int i,j; memset(prime,true,sizeof(prime)); for(i=2;i<N;i++) { if(prime[i]) { pr[k++]=i; for(j=i+i;j<N;j+=i) { prime[j]=false; } } } } int phi(int n) { int rea=n,i; for(i=0;pr[i]*pr[i]<=n;i++) { if(n%pr[i]==0) { rea=rea-rea/pr[i]; while(n%pr[i]==0) n/=pr[i]; } } if(n>1) rea=rea-rea/n; return rea%p; } int quick_mod(int a,int b) { int ans=1; a%=p; while(b) { if(b&1) { ans=ans*a%p; b--; } b>>=1; a=a*a%p; } return ans; } int main() { int i,t,n,ans; isprime(); scanf("%d",&t); while(t--) { ans=0; scanf("%d%d",&n,&p); for(i=1;i*i<=n;i++) { if(i*i==n) ans=(ans+quick_mod(n,i-1)*phi(i))%p; else if(n%i==0) ans=(ans+quick_mod(n,i-1)*phi(n/i)+quick_mod(n,n/i-1)*phi(i))%p; } printf("%d\n",ans%p); } return 0; }