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

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了：

 1 #include<cstdio>
 2 #include<cstdlib>
 3 #include<cstring>
 4 #include<iostream>
 5 #include<algorithm>
 6 using namespace std;
 7 #define Maxn 35000
 8 
 9 int n,p;
10 int pri[Maxn],phi[Maxn],pl;
11 int d[Maxn],dl;
12 bool vis[Maxn];
13 
14 void init()
15 {
16     pl=0;
17     memset(vis,0,sizeof(vis));
18     for(int i=2;i<=Maxn-110;i++)
19     {
20         if(vis[i]==0)
21         {
22             pri[++pl]=i;
23             phi[i]=i-1;
24         }
25         for(int j=1;j<=pl;j++)
26         {
27             if(i*pri[j]>Maxn-110) break;
28             vis[i*pri[j]]=1;
29             if(i%pri[j]!=0) phi[i*pri[j]]=phi[i]*(pri[j]-1);
30             else phi[i*pri[j]]=phi[i]*pri[j];
31             if(i%pri[j]==0) break;
32         }
33     }
34     phi[1]=1;
35     // for(int i=2;i<=10;i++) printf("%d ",phi[i]);
36     // printf("
");
37 }
38 
39 int qpow(int a,int b,int p)
40 {
41     a%=p;
42     int ans=1;
43     while(b)
44     {
45         if(b&1) ans=(ans*a)%p;
46         a=(a*a)%p;
47         b>>=1;
48     }
49     return ans;
50 }
51 
52 void get_d(int n)
53 {
54     dl=0;
55     for(int i=1;i<=pl;i++) if(n%pri[i]==0)
56     {
57         while(n%pri[i]==0) n/=pri[i];
58         d[++dl]=pri[i];
59     }
60     if(n!=1) d[++dl]=n;
61 }
62 
63 int gphi(int x)
64 {
65     int ans=x;
66     for(int i=1;i<=dl;i++) if(x%d[i]==0)
67     {
68         ans=ans/d[i]*(d[i]-1);
69     }
70     return ans;
71 }
72 
73 int main()
74 {
75     int T;
76     scanf("%d",&T);
77     init();
78     while(T--)
79     {
80         scanf("%d%d",&n,&p);
81         get_d(n);
82         int ans=0;
83         for(int i=1;i*i<=n;i++) if(n%i==0)
84         {
85             ans=(ans+(qpow(n,i-1,p)*(gphi(n/i)%p)))%p;
86             if(i*i!=n) ans=(ans+(qpow(n,n/i-1,p)*(phi[i]%p)))%p;
87         }
88         printf("%d
",ans);
89     }
90     return 0;
91 }

View Code

2017-01-13 11:48:09