一类解决字符串问题的有力工具。
$\mu$函数
貌似根据定义做就可以。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16void calmu(int n) {
np[1] = true; mu[1] = 1;
for(int i = 2; i <= n; i++) {
if(!np[i]) prime[++pos] = i , mu[i] = -1;
for(int j = 1; j <= pos && i * prime[j] <= n; j++) {
np[i * prime[j]] = 1;
if(i % prime[j]) {
mu[i * prime[j]] = -mu[i];
}
else {
mu[i * prime[j]] = 0;
break;
}
}
}
}
$\varphi$函数
考虑硬拆式子。
重温$\text{Euler Sieve}$的过程，就是找$n$的最小质因子$p_1$将其用$p_1 \times (n / p_1)$筛掉。
先设$n’ = n / p_1$，再分两种情况讨论：
$①:n’$有$p_1$这一因子。意味着唯一分解中$k_1 > 1$
那么显然，$n’$有着$n$的所有质因子。所以
$②:n’$没有$p_1$这一因子。意味着唯一分解中$k_1 = 1$
（其实也证明了欧拉函数是积性函数）
愉快的筛就好了。注意任何积性函数都有$f(1) = 1$.1
2
3
4
5
6
7
8
9
10
11
12
13
14
15void Euler_Sieve(int x) {
np[1] = 1; phi[1] = 1;
Go(i , 2 , x) {
if(!np[i]) prime[++cnt] = i , phi[i] = i - 1;
for(int j = 1; j <= cnt && i * prime[j] <= x; j++) {
np[i * prime[j]] = 1;
if(i % prime[j])
phi[i * prime[j]] = phi[i] * (prime[j] - 1);
else {
phi[i * prime[j]] = prime[j] * phi[i];
break;
}
}
}
}
Update your browser to view this website correctly. Update my browser now