【POJ 2154】 Color （置换、burnside引理）

时间：2021-05-20 15:04:04
Color

Description

Beads of N colors are connected together into a circular necklace of N beads (N<=1000000000). Your job is to calculate how many different kinds of the necklace can be produced. You should know that the necklace might not use up all the N colors, and the repetitions that are produced by rotation around the center of the circular necklace are all neglected.

You only need to output the answer module a given number P.

Input

The first line of the input is an integer X (X <= 3500) representing the number of test cases. The following X lines each contains two numbers N and P (1 <= N <= 1000000000, 1 <= P <= 30000), representing a test case.

Output

For each test case, output one line containing the answer.

Sample Input

5

1 30000

2 30000

3 30000

4 30000

5 30000

Sample Output

1

3

11

70

629

Source

【分析】　　

　　经典的置换和burnside引理应用。只有旋转。

　　考虑旋转i个单位，那么循环节有gcd(n,i)个

　　可以化出求 sigma(n^gcd(i,n))/n

　　根据莫比乌斯反演得 sigma(n^d*phi[n/d])/n   (d|n) 【表示我莫比乌斯反演白学了ORZ

　　即sigma(n^(d-1)*phi[n/d]) (d|n)

　　就算一算就好了。【不用欧拉筛，筛不到n的，先求出n的质因子，那么d的质因子也在里面，然后根据定义分解质因数求phi

　　最后要除以n，不能求逆元哦，每次少乘一个n就好了。

　　然而我还WA着！！！！【AC了再放代码吧

　　好了AC了：

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 using namespace std;

 #define Maxn 35000

 int n,p;

 int pri[Maxn],phi[Maxn],pl;

 int d[Maxn],dl;

 bool vis[Maxn];

 void init()

 {

     pl=;

     memset(vis,,sizeof(vis));

     for(int i=;i<=Maxn-;i++)

     {

         if(vis[i]==)

         {

             pri[++pl]=i;

             phi[i]=i-;

         }

         for(int j=;j<=pl;j++)

         {

             if(i*pri[j]>Maxn-) break;

             vis[i*pri[j]]=;

             if(i%pri[j]!=) phi[i*pri[j]]=phi[i]*(pri[j]-);

             else phi[i*pri[j]]=phi[i]*pri[j];

             if(i%pri[j]==) break;

         }

     }

     phi[]=;

     // for(int i=2;i<=10;i++) printf("%d ",phi[i]);

     // printf("\n");

 }

 int qpow(int a,int b,int p)

 {

     a%=p;

     int ans=;

     while(b)

     {

         if(b&) ans=(ans*a)%p;

         a=(a*a)%p;

         b>>=;

     }

     return ans;

 }

 void get_d(int n)

 {

     dl=;

     for(int i=;i<=pl;i++) if(n%pri[i]==)

     {

         while(n%pri[i]==) n/=pri[i];

         d[++dl]=pri[i];

     }

     if(n!=) d[++dl]=n;

 }

 int gphi(int x)

 {

     int ans=x;

     for(int i=;i<=dl;i++) if(x%d[i]==)

     {

         ans=ans/d[i]*(d[i]-);

     }

     return ans;

 }

 int main()

 {

     int T;

     scanf("%d",&T);

     init();

     while(T--)

     {

         scanf("%d%d",&n,&p);

         get_d(n);

         int ans=;

         for(int i=;i*i<=n;i++) if(n%i==)

         {

             ans=(ans+(qpow(n,i-,p)*(gphi(n/i)%p)))%p;

             if(i*i!=n) ans=(ans+(qpow(n,n/i-,p)*(phi[i]%p)))%p;

         }

         printf("%d\n",ans);

     }

     return ;

 }

2017-01-13 11:48:09

相关文章