就那个常用卷积
$id_k * 1 = \sigma_k$
$\mu * id = \phi$
$\phi * 1 = id$
$\mu * 1 = \epsilon$
$\sigma_0 * \mu = 1$
就那个狄利克雷前/后缀和
$O(nlog(logn))$
$g(d)=\sum \limits _{d|T}f(T)$
for (int i = 0; i < cnt; i++) {
for (int j = n / primes[i]; j; j--) {
f[j] += f[j * primes[i]];
}
}
$g(T)=\sum \limits _{d|T}f(d)$
for (int i = 0; i < cnt; i++) {
for (int j = 1; j * primes[i] <= n; j++) {
f[primes[i] * j] += f[j];
}
}
就那个伯努利数和自然数幂和多项式的系数
$O(n^2)$
void init_B(int n) {
B[0] = 1;
for (int i = 1; i <= n; i++) {
int sum = 0;
for (int j = 0; j < i; j++) {
sum = (sum + 1ll * c(i + 1, j) * B[j] % mod) % mod;
}
B[i] = (mod - 1ll * sum * qpow(c(i + 1, i), mod - 2) % mod);
}
for (int i = 0; i <= n; i++) {
f[n + 1 - i] = 1ll * c(n + 1, i) * B[i] % mod * qpow(n + 1, mod - 2) % mod;
}
}