POJ2154(Pólya定理与欧拉函数优化)

题目：Color

题意：将正n边形的n个顶点用n种颜色染色，问有多少种方案（答案mod p，且可由旋转互相得到的算一种）

先说说Pólya定理

设Q是n个对象的一个置换群，用m种颜色涂染这n个对象，一个对象涂任意一种颜色，则在Q作用下不等价的方案数为:   

|Q|为置换群中置换的个数，

分析可以知道本题方案的表达式为：

然后就直接代码了：

#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;
}