欧拉函数

POJ-2154 Color

置换群,burnside引理的题目。

这道题代表了一类题目的优化

裸的算法是 ∑n^(gcd(n,i)) 1<i<=n

复杂度过高,进行优化。

置换群种循环的个数L = n / gcd(n, i)

因为如果L | n, 则有n / L | n

则环的长度L的范围是1 ~ sqrt(L)

令a = gcd(n, i), 设i = at

则只有i与t互质的时候,gcd(i, t) = a

则最后可以优化为 ∑(Φ(i) * n ^ (i)) % p