前置相关
-
类型积性函数（注：以下皆为完全积性函数，即无需满足 (x perp y) 即有 (f(x)f(y) = f(xy))
(epsilon (n) = [n = 1])
(id (n) = n)
-
狄利克雷卷积与欧拉函数
此处若以 $id $ 作单位元，则 (1) 为 (phi) 的逆，即 (phi * 1 = id)
证明：由 (sumlimits_{d | n} phi (d) = n) ，再带回原式可证
-
莫比乌斯函数与欧拉函数的转化
[egin{aligned} phi * 1 &= id \ phi * 1 * mu &= id * mu \ phi * epsilon &= id * mu \ phi &= sumlimits_{d | n} mu(d) frac{n}{d} \ frac{phi}{n} &= sumlimits_{d | n} frac{mu(d)}{d} end{aligned} ]
杜教筛
-
杜教筛用于求解积性函数前缀和一类问题
-
下面求解积性函数 (f) 的前缀和
-
设积性函数 (f, g, h) ，且 (h = f * g) ，则有
[egin{aligned} sumlimits_{i = 1}^n h(n) &= sumlimits_{i = 1}^n sumlimits_{d | n} g(d)f(frac{n}{d}) \ &= sumlimits_{d = 1}^n g(d) sumlimits_{i = 1}^{leftlfloorfrac{n}{d}
ight
floor} f(i) end{aligned}
]
- 令 (S(n) = sumlimits_{i = 1}^n f(i))
- 将 (d = 1) 时的提出，再移项，得
[S(n) = sumlimits_{i = 1}^n h(i) - sumlimits_{d = 2}^n g(d)S(leftlfloorfrac{n}{d}
ight
floor)
]
- 那么预处理 (h, g) 的前缀和（一般预处理 (n^{frac{2}{3}}) 个？），再递归整除分块即可处理，不过一般 (h, g) 需要自己配
例
- 求(sumlimits_{i = 1}^n mu(i), sumlimits_{i = 1}^n phi(i))
由 (mu * 1 = epsilon) ，可令 (g = 1, h = epsilon) ，那么得到
[S(n) = 1 - sumlimits_{d = 2}^n S(leftlfloorfrac{n}{d}
ight
floor)
]
求 (sum phi) 同理
- 求(sumlimits_{i = 1}^n i phi(i)) （需要用配的）
[h(n) = sumlimits_{d | n} d phi(d) g(frac{n}{d})
]
希望将 (d) 消去，故配 (g = id) ，得 (h(n) = n^2)
[S(n) = sumlimits_{i = 1}^n i^2 - sumlimits_{d = 2}^n d S(leftlfloorfrac{n}{d}
ight
floor)
]
即可解
代码（求解(sum mu, sum phi) ）##
#include <iostream>
#include <cstdio>
#include <cstring>
#include <tr1/unordered_map>
using namespace std;
typedef long long LL;
const int MAXN = 5e06 + 10;
int prime[MAXN / 10];
int vis[MAXN]= {0};
int pcnt = 0;
int mu[MAXN]= {0};
LL phi[MAXN]= {0};
int sumu[MAXN]= {0};
LL sumphi[MAXN]= {0};
const int MAX = 4e06 + 5e05;
void linear_sieve () {
mu[1] = phi[1] = 1;
for (int i = 2; i <= MAX; i ++) {
if (! vis[i]) {
prime[++ pcnt] = i;
mu[i] = - 1, phi[i] = i - 1;
}
for (int j = 1; j <= pcnt && i * prime[j] <= MAX; j ++) {
vis[i * prime[j]] = 1;
if (! (i % prime[j])) {
phi[i * prime[j]] = phi[i] * prime[j];
break;
}
mu[i * prime[j]] = - mu[i];
phi[i * prime[j]] = phi[i] * (prime[j] - 1);
}
}
for (int i = 1; i <= MAX; i ++) {
sumu[i] = sumu[i - 1] + mu[i];
sumphi[i] = sumphi[i - 1] + phi[i];
}
}
int T;
int N;
tr1::unordered_map<int, int> mapmu;
tr1::unordered_map<int, LL> maphi;
int mu_sieve (int n) {
if (n <= MAX)
return sumu[n];
if (mapmu[n])
return mapmu[n];
int total = 1;
for (int l = 2, r; l <= n; l = r + 1) {
r = n / (n / l);
total -= (r - l + 1) * mu_sieve (n / l);
}
return mapmu[n] = total;
}
LL phi_sieve (int n) {
if (n <= MAX)
return sumphi[n];
if (maphi[n])
return maphi[n];
LL total = n * 1ll * (n + 1) / 2ll;
for (int l = 2, r; l <= n; l = r + 1) {
r = n / (n / l);
total -= 1ll * (r - l + 1) * phi_sieve (n / l);
}
return (maphi[n] = total);
}
int main () {
linear_sieve ();
scanf ("%d", & T);
for (int Case = 1; Case <= T; Case ++) {
scanf ("%d", & N);
LL ans1 = phi_sieve (N);
int ans2 = mu_sieve (N);
printf ("%lld %d
", ans1, ans2);
}
return 0;
}
/*
6
1
2
8
13
30
2333
*/
/*
5
1880071
7261727
9181941
8084555
3730126
*/