线性筛
线性筛可以在严格 \(O(n)\) 的时间内筛出积性函数的值
拥有常见的套路。
假设 \(n = p_1^{a_1} p_2^{a_2} \dots p_k^{a_k}\)
如果我们能快速得到 \(f(p_i),f(p_i^{k+1})\) 的取值，那么直接套板子即可。
定义：
\(p_i\) 表示 \(n\) 分解质因数后第 \(i\) 个质数，\(a_i\) 表示 \(p_i\) 的指数。
筛素数：
- 判断 \(n\) 是否标记
- 无标记，\(n\) 则为素数，并将 \([n,n^2]\) 打标记
- 否则为偶数，直接跳过
莫比乌斯函数：
根据定义：
\[\mu =\begin{cases}\left( -1\right) ^{k}\left( n=p_{1}p_{2}\ldots p_{k}\right) \\ 0\left( \exists P^{2}|n\right) \\ 1\left( n=1\right) \end{cases}
\]
const int MAXN = 1e4 + 10;
int N, prime[MAXN], vis[MAXN], mu[MAXN], tot;
void GetMu(int N) {
vis[1] = mu[1] = 1;
for(int i = 2; i <= N; i++) {
if(!vis[i]) prime[++tot] = i, mu[i] = -1;
for(int j = 1; j <= tot && i * prime[j] <= N; j++) {
vis[i * prime[j]] = 1;
if(!(i % prime[j])) {
mu[i * prime[j]] = 0; break;
}
mu[i * prime[j]] = mu[i] * mu[prime[j]];
//根据莫比乌斯函数的定义，这里也可以写为
//mu[i * prime[j]] = -mu[i];
}
}
}
欧拉函数：
int N, prime[MAXN], vis[MAXN], phi[MAXN], tot;
void GetPhi(int N) {
vis[1] = phi[1] = 1;
for(int i = 2; i <= N; i++) {
if(!vis[i]) prime[++tot] = i, phi[i] = i - 1;
for(int j = 1; j <= tot && i * prime[j] <= N; j++) {
vis[i * prime[j]] = 1;
if(!(i % prime[j])) {
phi[i * prime[j]] = phi[i] * prime[j];
break;
}
phi[i * prime[j]] = phi[i] * phi[prime[j]];
}
}
}
约数个数：
我们需要考虑最小的质因子对每个数的贡献。
\[n = p_1^{a_1} p_2^{a_2} \dots p_k^{a_k}
\]
设 \(d(i)\) 表示 \(i\) 的约数个数，我们根据约数定理：
\[d(i) = \prod_{i = 1}^k (a_i + 1)
\]
记 \(a(i)\)表示 \(n\) 的最小的质因子 \((a_1)\) 的指数, \(d(pi)=2\)
当 \(i\) 时，考虑 \(i?p_j\) ，实际上也就是 \(a_i\) 的指数多了1
我们先除去原来的，再加上新的就彳亍了
int N, prime[MAXN], vis[MAXN], D[MAXN], a[MAXN], tot;
void GetD(int N) {
vis[1] = D[1] = a[1] = 1;
for(int i = 2; i <= N; i++) {
if(!vis[i]) prime[++tot] = i, D[i] = 2, a[i] = 1;
for(int j = 1; j <= tot && i * prime[j] <= N; j++) {
vis[i * prime[j]] = 1;
if(!(i % prime[j])) {
D[i * prime[j]] = D[i] / (a[i] + 1) * (a[i] + 2);
a[i * prime[j]] = a[i] + 1;
break;
}
D[i * prime[j]] = D[i] * D[prime[j]];
a[i * prime[j]] = 1;
}
}
}
约数和：
我们设 \(SD(i)\) 表示 \(i\) 的约数和,有式子：
\[SD(n) = \prod_{i = 1}^k (\sum_{j = 1}^{a_i} p_i^j)
\]
\(sum(i)\) 表示 \(i\) 最小的质因子的贡献，即 \(sum(i) = \sum_{i = 1}^{a_1}p_1^j\)
\(low(i)\) 表示 \(i\) 最小质因子的指数，\(low(i)=a_1\)
有了这三个我们就可以转移了
同样是考虑 \(i\) 的最小的因子对答案的贡献
int N, prime[MAXN], vis[MAXN], SD[MAXN], sum[MAXN], low[MAXN], tot;
void GetSumD(int N) {
vis[1] = SD[1] = low[1] = sum[1] = 1;
for(int i = 2; i <= N; i++) {
if(!vis[i]) prime[++tot] = i, sum[i] = SD[i] = i + 1, low[i] = i;
for(int j = 1; j <= tot && i * prime[j] <= N; j++) {
vis[i * prime[j]] = 1;
if(!(i % prime[j])) {
low[i * prime[j]] = low[i] * prime[j];
sum[i * prime[j]] = sum[i] + low[i * prime[j]];
SD[i * prime[j]] = SD[i] / sum[i] * sum[i * prime[j]];
break;
}
low[i * prime[j]] = prime[j];
sum[i * prime[j]] = prime[j] + 1;
//这里low和sum不是积性函数
SD[i * prime[j]] = SD[i] * SD[prime[j]];
}
}
}