POJ2154 - Click Here
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.
Solutions
POJ2409的加强版。
和POJ2409不同的是，没有了翻转的置换，因此仅需要考虑旋转的置换。显然，旋转的置换成群。
注意到对于每个置换，置换前的元素与置换后的元素的差值是定值，因此循环分解后，每个循环的长度是一样的。
现在设这个定值为$k$，每个循环的长度为$l$，则易得$n \mid kl$。
最小满足这个式子的$l=\frac{n}{gcd(k,n)}$，对应的循环数为$\frac{n}{l}=gcd(k,n)$
再套用Polya可得$ans = \frac{1}{n} \sum_{k=1}^n n^{gcd(k,n)} = \sum_{k=1}^n n^{gcd(k,n)-1}$
暴力做的话，时间复杂度是$O(XN \, log \, N)$
考虑进一步优化，利用BZOJ2705的思路可将该式转换为$ans = \sum_{d \mid n} n^{d-1} \phi(\frac{n}{d})$
暴力求欧拉函数的时间复杂度为$O(XN)$
但由于约数个数不会太多，因此这个上界十分宽松，大概可以认为是$O(X\sqrt N)$的。
CODE
CODE - Click Here