线性筛筛一般积性函数
前置芝士
- 线性筛、积性函数
有用的结论
- 设 \(f(x)\) 和 \(g(x)\) 都是积性函数，则 \(h(x)=f(x)g(x)\) 也是积性函数
- 设 \(f(x)\) 和 \(g(x)\) 都是积性函数，则 \(h(x \cdot y)=\sum\limits_{x\cdot y=n}f(x)g(y)\) 也是积性函数
How to do
给定一个积性函数 \(f(x)\)
要求能快速计算 \(f(p)\) 和 \(f(p^{k})\) 其中 \(p\) 为质数
对于每个数 \(x\)，记录它最小的质因子的幂 记为 \(low[n]\) 比如 \(low[60]=2^{2}=4\)
若 \(x\) 的最小质因子 \(p\) 指数为一，那么直接套用公式 \(f(x\cdot y)=f(x)
\cdot f(y)\)
否则分两类讨论：
若 \(x=p^{k}\) 根据 \(f(p^{k-1})\)计算 \(f(p^k)\)
否则把 \(x\) 分解成 \(\frac{x}{low[x]}\) 和 \(low[x]\) 再使用上面公式计算
example1:
- 筛 \(f(n)=\sum\limits_{d|n} d \cdot \varphi(d)\)
f[1] = 1;
for (int i = 2; i <= n; i++)
{if (low[i] == 0){low[i] = i, prime.emplace_back(i);f[i] = 1ll * (i - 1) * i + 1ll;}for (auto j : prime){if (i * j > n)break;if (i % j == 0){low[i * j] = low[i] * j;if (low[i] == i){f[i * j] = f[i] + 1ll * (i * j - i) * (i * j);}else{f[i * j] = f[i / low[i]] * f[low[i] * j];}break;}low[i * j] = j;f[i * j] = f[i] * f[j];}
}
lazytag