Contents
核心柿子
我们要求积性函数 f 的前缀和。设：
S(n)=\sum_{i=1}^{n}f(i)
我们找到另一个积性函数 g，则有：
g(1)S(n)=\sum_{i=1}^{n}(f * g)(i)-\sum_{i=2}^{n}g(i)\cdot S\left(\left\lfloor\frac{n}{i}\right\rfloor\right)
如果能快速求出 f * g 和 g 的前缀和，就可以数论分块求解 f 的前缀和。
一些好用的狄利克雷卷积结果
\begin{aligned}
\mu * I &= \varepsilon\cr \varphi * I &= if\cr d &= I * I\cr
\left(\varphi(i)\cdot i\right) * i &=\sum_{d|n}(\varphi(d)\cdot d)\cdot\frac{n}{d}=i^2\cr
\left(\varphi(i)\cdot i^2\right) * i^2 &=\sum_{d|n}(\varphi(d)\cdot d^2)\cdot\frac{n}{d^2}=i^3\cr
\left(\mu(i)\cdot i\right) * i &=\sum_{d|n}(\mu(d)\cdot d)\cdot\frac{n}{d}=i\cr
\left(\mu * id^2\right) * I &=\left(\mu * I\right) * id^2=\varepsilon * id^2=id^2
\end{aligned}
筛 mu 和 phi
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 5e6 + 50;
unordered_map<int, int> Summu;
unordered_map<int, ll> Sumphi;
int T, n;
int maxup;
ll phi[N], Sphi[N];
int mu[N], Smu[N];
int num[N], prime[N], tot;
void init(int n) {
maxup = max(1e6, pow(n, 2.0/3.0));
mu[1] = 1; phi[1] = 1;
for (int i = 2; i < maxup; i++) {
if (!num[i]) {
prime[++tot] = i;
mu[i] = -1;
phi[i] = i - 1;
}
for (int j = 1, x; j <= tot && (x = i * prime[j]) < maxup; j++) {
num[x] = 1;
if (i % prime[j]) {
mu[x] = -mu[i];
phi[x] = phi[i] * phi[prime[j]];
}
else {
phi[x] = phi[i] * prime[j];
break;
}
}
}
//求前缀和
for(int i = 1; i < maxup; i++) {
Smu[i] = Smu[i-1] + mu[i];
Sphi[i] = Sphi[i-1] + phi[i];
}
}
int Get_Sum_mu(int x) {
if (x < maxup) return Smu[x];
if (Summu[x]) return Summu[x];
int ret = 1; //卷积得到的\varepsilon前缀和为1
for (int l = 2, r; l <= x; l = r + 1) {
r = x / (x / l);
ret -= (r - l + 1) * Get_Sum_mu(x / l);
// 在l到r区间内I函数的和为r-l+1
}
return Summu[x] = ret;
}
ll Get_Sum_phi(int x) {
if (x < maxup) return Sphi[x];
if (Sumphi[x]) return Sumphi[x];
ll ret = 1LL * x * (x + 1) / 2; // 卷积得到的id的前缀和
for (int l = 2, r; l <= x; l = r+1) {
r = x / (x / l);
ret -= 1LL * (r - l + 1) * Get_Sum_phi(x / l) ;
}
return Sumphi[x] = ret;
}
int main() {
init(INT_MAX);
scanf("%d", &T);
while(T--) {
scanf("%d", &n);
printf("%lld %d\n", Get_Sum_phi(n), Get_Sum_mu(n));
}
return 0;
}
应用举例
简单例子
题目大意：
\left(\sum_{i=1}^n\sum_{j=1}^n ij \gcd(i,j)\right) \bmod p
题目分析：
\begin{aligned}
原式&=\sum_dd\sum_{i=1}^n\sum_{j=1}^n ij [\gcd(i,j)=d]\cr
&=\sum_dd^3\sum_{i=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\sum_{j=1}^{\left\lfloor\frac{n}{d}\right\rfloor} ij [\gcd(i,j)=1]\cr
设g(n)&=1^3+2^3+\cdots+n^3=\frac{n^2(n+1)^2}{4}\cr
设f(n)&=\sum_{i=1}^n\sum_{j=1}^n ij [\gcd(i,j)=1]\cr
&=\sum_{i=1}^n\sum_{j=1}^n ij \sum_{d|\gcd(i,j)}\mu(d)\cr
&=\sum_{d=1}^{n}d^2\mu(d)\cdot g\left(\left\lfloor\frac{n}{d}\right\rfloor\right)
\end{aligned}
\begin{aligned}
\therefore 原式&=\sum_{d=1}^{n}d^3\cdot f\left(\left\lfloor\frac{n}{d}\right\rfloor\right)\cr
&=\sum_{d=1}^{n}d^3\sum_{x=1}^{\left\lfloor\frac{n}{d}\right\rfloor}x^2\mu(x)\cdot g\left(\left\lfloor\frac{n}{xd}\right\rfloor\right)\cr
\end{aligned}
观察到前两个和式顶部之积为 n，因此枚举 T=xd：
\begin{aligned}
&=\sum_{T=1}^{n}g\left(\left\lfloor\frac{n}{T}\right\rfloor\right)T^2\sum_{x|T}^{T}\mu(x)\cdot \frac{T}{x}\cr
&=\sum_{T=1}^{n}g\left(\left\lfloor\frac{n}{T}\right\rfloor\right)\cdot T^2\varphi(T)
\end{aligned}
T^2\varphi(T) 可用杜教筛求前缀和，然后对整个柿子整除分块即可。