[poj] 2154: Color

发表于   |   分类于   |  

题意

用n种颜色对n个珠子构成的环上色, 旋转后相同的只算一种, 求本质不同的着色方案数

传送门

分析

由 $burnside$ 定理可知, 有n个置换, 每个置换使得着色不变的着色方案个数有 $gcd(n,i)$ 个
由于$n\le 10^9$那么不能直接枚举, 那么

$$
\begin{aligned}
ans&=\frac{1}{n}\cdot \sum_{i=1}^{n}n^{gcd(n,i)}\\
&=\frac{1}{n}\cdot \sum_{d|n}\cdot n^{d}\cdot\sum_{i=1}^{n} \varepsilon(gcd(n,i)=d)\\
&=\frac{1}{n}\cdot \sum_{d|n}\cdot n^{d}\cdot\sum_{i=1}^{\frac{n}{d}} \varepsilon(gcd(\frac{n}{d},i)=1)\\
&=\frac{1}{n}\cdot\sum_{d|n}\cdot n^{d}\cdot\varphi(\frac{n}{d})\\
&=\sum_{d|n}\cdot n^{d-1}\cdot\varphi(\frac{n}{d})
\end{aligned}
$$

此时不能直接用筛法求出欧拉函数值并存下来, 所以需要在线求欧拉函数

已知

$$n=\sum_{d|n}\varphi(d)$$

由莫比乌斯进行反演得

$$\varphi(n)=\sum_{d|n} \mu(d) \cdot (\frac{n}{d})$$

又因为$\mu(n)$的定义

$$\mu(n) =
\begin{cases}
1, & \text{$n$ = 1} \\
(-1)^k, & \text{$n$无平方因子} \\
0, & \text{其它}
\end{cases}
$$

所以求$\varphi(n)$时,并不需要那些有平方因子的$d$

由唯一分解定理得
$$n=a_1^{p_1}\cdot a_2^{p_2}\cdot a_3^{p_3}\cdots a_k^{p_k}$$
其中的$a_i$为质数

那么我们只需要枚举一下由几个$a_i$相乘得到的$d$再加上一个$d=1$的情况即可

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include <cstdio>

int ansmod ;

inline int POW(int x , int p) {
trueint ret = 1 ;
truefor (x%=ansmod ; p ; p>>=1 , x*=x , x%=ansmod)
truetrueif (p&1) ret*=x , ret%=ansmod ;
truereturn ret ;
}

#include <vector>
#include <cmath>

#define  sqr(x)  ((x)*(x))

#define  maxn  32000LL

std::vector<int> prime ;/* 素数 */
std::vector<int> factor ;/* 约数 */
std::vector<int> pfactor ;/* 质因数 */

bool cps[maxn] = {0} ;/* 合数 */

void GetPrime() {/* 得到所有质数 */
int i , j ;
trueprime.clear() ;
truefor (i = 2 ; i < 200 ; i ++ )
truetrueif (!cps[i]) for (j = i<<1 ; j < maxn ; j += i)
truetruetruecps[j] = true ;
truefor (i = 2 ; i < maxn ; i ++ )
truetrueif (!cps[i]) prime.push_back(i) ;
}

void GetFactor(int x) {/* 得到x的所有约数 */
int i , tmp ;
truefactor.clear() ;
truetmp = sqrt(x) ;
truefor (i = 1 ; i <= tmp ; i ++ ) {
truetrueif (x%i == 0) {
truetruetruefactor.push_back(i) ;
truetruetrueif (i!=(x/i)) factor.push_back(x/i) ;
truetrue}
true}
}

void Decps(int x) {/* 将x质因数分解 */
int i , tmp ;
truepfactor.clear() ;
truetmp = sqrt(x) ;
truefor (i = 0 ; prime[i] <= tmp ; i ++ )
truetrueif (x%prime[i] == 0) {
truetruetruepfactor.push_back(prime[i]) ;
truetruetruewhile (x%prime[i] == 0) x /= prime[i] ;
truetrue}
trueif (x > 1) pfactor.push_back(x) ;
}

int CalcD(int s , int& mu) {/* 计算出由s表示的某一个不含平方因子的数,并求得\mu值 */
int ret = 1 , i ;
truefor (i = mu = 0 ; s ; s>>=1 , i ++ )
truetrueif (s&1) ret *= pfactor[i] , mu ++ ;
truemu = (mu&1) ? -1 : 1 ;
truereturn ret ;
}

int Euler(int x) {
int s , k , d , mu , ret = 0 ;
trueDecps(x) ;
truek = pfactor.size() ;
truefor (s = 1 ; s < (1<<k) ; s ++ ) {
truetrued = CalcD(s , mu) ;
truetrueret += x/d*mu ;
true}
trueret = (x+ret)%ansmod ;
truereturn ret ;
}

int main() {
int Time , n , i , ans ;
//	#define READ
true#ifdef  READ
truetruefreopen(".in" ,"r",stdin ) ;
truetruefreopen(".out","w",stdout) ;
true#endif
trueGetPrime() ;
truescanf("%d", &Time) ;
truewhile (Time-->0) {
truetruescanf("%d%d", &n , &ansmod) ;
truetrueGetFactor(n) ;
truetrueans = 0 ;
truetruefor (i = 0 ; i < factor.size() ; i ++ ) {
truetruetrueans += POW(n,factor[i]-1)*Euler(n/factor[i]) ;
truetruetrueans %= ansmod ;
truetrue}
truetrueprintf("%d\n", ans) ;
true}
true#ifdef  READ
truetruefclose(stdin) ; fclose(stdout) ;
true#else
truetruegetchar() ; getchar() ;
true#endif
truereturn 0 ;
}

热评文章