【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

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

2017-01-13 11:48:09

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

原文：http://www.cnblogs.com/Konjakmoyu/p/6282168.html