POJ 2154 Color （Polya + 欧拉函数）

POJ 2154 Color （Polya + 欧拉函数）

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

51 300002 300003 300004 300005 30000

Sample Output

131170629

题意

有 ​​N​​​ 种颜色的珠子要组成长度为 ​​N​​ 的项链，考虑旋转相同的情况算一种，求总共有多少种情况 mod P 。

思路

从题意来看是一道 ​​Polya​​ 计数问题，于是我们想到公式 L=1|G|×∑kC(f),f∈G ，其中 C(f) 为置换 f 的循环节个数， |G|

因为只需要考虑旋转置换，于是 C(fi)=gcd(n,i) ， i 表示一次转过 i 颗珠子，当 i=0 时， C(f0)=N

再看 N 的范围： [1,1000000000] ，显然我们不能一一枚举每一个 i

于是分析 C(fi)=x 在所有的 gcd(n,i)

显然 gcd(n,i)=x 等同于 gcd(nx,ix)=1 ，然后我们可以知道其出现次数便是 nx 的欧拉函数（其中 x 为 n

然后公式便被我们转化为了： L=1|G|×∑i|N(ki×phi[N/i])

素数表的辅助可以更快的求解欧拉函数的值，然后我们在枚举 N 的因子时遍历长度只需要小于等于 N−−√

AC 代码

#include#include#include#include#include#include#include#include

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。