# 积性函数的线性筛法总结

### 原理

void init() {
phi[1] = 1;
for (int i = 2; i <= N; ++i) {
if (!p[i])
pr[++pr[0]] = i, phi[i] = i - 1;
for (int j = 1; j <= pr[0] && i * pr[j] <= N; ++j) {
p[i * pr[j]] = 1;
if (i % pr[j] == 0) {
phi[i * pr[j]] = phi[i] * pr[j];
break;
}
phi[i * pr[j]] = phi[i] * phi[pr[j]];
}
}
}


i % pr[j] != 0的时候，这两个数就是互质的，那么可以直接相乘。

i % pr[j] == 0的时候，每个积性函数都不是相同的，都需要化下式子。比如$\varphi$来说，可以得到$\varphi(ab) = \varphi(a)b\;\;(a \%b=0)$

### 例题

#### bzoj 1968

##### 题解

#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1000000;
bool p[N + 10];
int n, t[N + 10], pr[N + 10];
long long k, ans, d[N + 10];
void init(int n) {
d[1] = 1, t[1] = 0;
for (int i = 2; i <= n; ++i) {
if (!p[i])
pr[++pr[0]] = i, d[i] = 2, t[i] = 1;
for (int j = 1; j <= pr[0] && i * pr[j] <= n; ++j) {
p[i * pr[j]] = 1;
if (i % pr[j] == 0) {
d[i * pr[j]] = d[i] / (t[i] + 1) * (t[i] + 2);
t[i * pr[j]] = t[i] + 1;
break;
}
d[i * pr[j]] = d[i] * d[pr[j]];
t[i * pr[j]] = 1;
}
}
}
main() {
scanf("%d", &n);
init(n);
for (int i = 1; i <= n; ++i)
ans += d[i];
printf("%lld\n", ans);
}


#### BZOJ2813

##### 题解

#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 10000000, mod = 1000000007;
bool p[N + 10];
int n, T, a, b, c, t[N + 10], pr[N + 10];
long long k, ans1, ans2, d[N + 10], r[N + 10], g[N + 10];
void init(int n) {
r[1] = d[1] = 1;
for (int i = 2; i <= n; ++i) {
if (!p[i])
pr[++pr[0]] = i, d[i] = 2, t[i] = g[i] = 1,
r[i] = (1ll * i * i + 1ll) % mod;
for (int j = 1; j <= pr[0] && i * pr[j] <= n; ++j) {
p[i * pr[j]] = 1;
if (i % pr[j] == 0) {
d[i * pr[j]] = (1ll * d[i] / (t[i] + 1ll) * (t[i] + 2ll)) % mod;
t[i * pr[j]] = t[i] + 1;
g[i * pr[j]] = g[i];
r[i * pr[j]] = (r[g[i]] + 1ll * r[i] * pr[j] % mod * pr[j] % mod) % mod;
break;
}
d[i * pr[j]] = d[i] * d[pr[j]];
t[i * pr[j]] = 1;
g[i * pr[j]] = i % mod;
r[i * pr[j]] = (r[i] + 1ll * r[i] * pr[j] % mod * pr[j] % mod) % mod;
}
}
}
main() {
scanf("%d%d%d%d%d", &T, &n, &a, &b, &c);
init(c);
while (T--) {
long long tmp;
tmp = d[n] + ((n & 1) ? 1 : 0);
ans1 = (ans1 + tmp) % mod;
tmp = r[n] + ((n & 1) ? 4 : 0);
ans2 = (ans2 + tmp) % mod;
n = (1ll * n * a + b) % c + 1;
}
printf("%lld\n%lld\n", ans1, ans2);
}


#### BZOJ4407

##### 题意

$$\sum_{i = 1}^n\sum_{j = 1}^m(i,j)^k$$

##### 题解

\large \begin{aligned} &\;\;\;\;\; \sum_{i = 1}^n\sum_{j = 1}^m (i,j)^k \\ &= \sum_d d^k \sum_{i = 1}^n\sum_{j = 1}^m [(i,j)=b] \\ &= \sum_d d^k \sum_{i = 1}^{n \over d}\sum_{j = 1}^{m \over d}[(i,j)=1] \\ &= \sum_d d^k \sum_{i = 1}^{n \over d}\sum_{j = 1}^{m \over d}\sum_{p|(i,j)} \mu(p) \\ &= \sum_d d^k \sum_p \mu(p) {n\over dp} {m\over dp} \\ &= \sum_d d^k \sum_p \mu(p) {n\over T} {m\over T} \\ &= \sum_{T = 1}^{min(n,m)} {n\over T} {m\over T} \sum_{d|T}d^k \mu({T\over d}) \end{aligned}

$$f(T)=\sum_{d|T}d^k\mu({T\over d})$$

#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 5000000, mod = 1000000007;
bool p[N + 10];
int T, pr[N + 10], n, m;
long long k, f[N + 10], ans;
long long fast\_pow(long long a, int p)
{
long long ans=1;
for (; p; p >>= 1, a = a * a % mod)
if (p & 1) ans = ans * a % mod;
return ans;
}
void init() {
f[1] = 1;
for (int i = 2; i <= N; ++i) {
if (!p[i])
pr[++pr[0]] = i, f[i] = (fast\_pow(i, k) - 1 + mod) % mod;
for (int j = 1; j <= pr[0] && i * pr[j] <= N; ++j) {
p[i * pr[j]] = 1;
if (i % pr[j] == 0) {
f[i * pr[j]] = f[i] * fast\_pow(pr[j], k) % mod;
break;
}
f[i * pr[j]] = f[i] * f[pr[j]] % mod;
}
}
for (int i = 2; i <= N; ++i) f[i] = (f[i] + f[i - 1]) % mod;
}
main() {
scanf("%d%d", &T, &k);
init();
while (T--) {
scanf("%d%d", &n, &m);
if (n > m) swap(n, m);
ans = 0;
for (int i = 1, las; i <= n; i = las + 1) {
las = min(n / (n / i), m / (m / i));
ans += (f[las] - f[i - 1]) * (n / i) % mod * (m / i) % mod;
ans = (ans % mod + mod) % mod;
}
printf("%lld\n", ans);
}
}