数论分块
讲解先咕咕，做杜教筛做错题了做了个数论分块，下次再讲。
题目示例
P3327 [SDOI2015] 约数个数和
设 \(d(x)\) 为 \(x\) 的约数个数，给定 \(n,m\)，求
\[\sum_{i=1}^n\sum_{j=1}^md(ij) \]对于 \(100\%\) 的数据，\(1\le T,n,m \le 50000\)。
\[\sum_{i=1}^n\sum_{j=1}^md(ij) = \sum_{i=1}^n\sum_{j=1}^m\sum_{d \mid ij} 1 \]
设 \(xy = d\)，考虑把 \(d\) 分解有什么情况，由于所有的 \(d\) 值是唯一的，所以每一个 \(x\) 和 \(y\) 的枚举需要唯一，不妨设 \(x \mid i\)，\(y \mid j\)，考虑 \(xy\) 什么时候唯一对应 \(ij\) 的因数。
可以发现，如果 \(xy\) 不能唯一对应 \(ij\) 的因数时，说明 \(xy\) 有多种拆解方式，而 \(x \mid i\)，\(y \mid j\)，因此，如果 \(x, y\) 含有共同的因子，这 \(xy\) 是可以再分的，因此所以它的充要条件是 \([\gcd(x, y) = 1]\)，原始可继续改写。
\[\sum_{i=1}^n\sum_{j=1}^m\sum_{d \mid ij} 1 = \sum_{i=1}^n\sum_{j=1}^m\sum_{x \mid i}\sum_{y \mid j}[\gcd(x, y) = 1] \]又有 \(x, y\) 的求和是独立的，可以改写。
\[\begin{aligned} \sum_{i=1}^n\sum_{j=1}^m\sum_{x \mid i}\sum_{y \mid j}[\gcd(x, y) = 1] &= \sum_{x = 1}^n\sum_{y = 1}^m\sum_{x \mid i}^n\sum_{y \mid j}^m[\gcd(x, y) = 1] ] \\ &= \sum_{x = 1}^n\sum_{y = 1}^m\bigg\lfloor\frac{n}{x}\bigg\rfloor\bigg\lfloor\frac{m}{y}\bigg\rfloor[\gcd(x, y) = 1] \\ \end{aligned} \]考虑莫比乌斯反演 \(\sum\limits_{d \mid n} \mu(d) = [n = 1]\)。
\[\begin{aligned} \sum_{x = 1}^n\sum_{y = 1}^m\bigg\lfloor\frac{n}{x}\bigg\rfloor\bigg\lfloor\frac{m}{y}\bigg\rfloor[\gcd(x, y) = 1] &= \sum_{x = 1}^n\sum_{y = 1}^m\bigg\lfloor\frac{n}{x}\bigg\rfloor\bigg\lfloor\frac{m}{y}\bigg\rfloor\sum_{d \mid \gcd(x, y)}\mu(d) \\ &= \sum_{d = 1}^n\mu(d)\sum_{d \mid x}^n\sum_{d \mid y}^m\bigg\lfloor\frac{n}{x}\bigg\rfloor\bigg\lfloor\frac{m}{y}\bigg\rfloor \\ &= \sum_{d = 1}^n\mu(d)\sum_{i = 1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j = 1}^{\lfloor\frac{m}{d}\rfloor}\bigg\lfloor\frac{n}{di}\bigg\rfloor\bigg\lfloor\frac{m}{dj}\bigg\rfloor \\ &= \sum_{d = 1}^n\mu(d)\left(\sum_{i = 1}^{\lfloor\frac{n}{d}\rfloor}\bigg\lfloor\frac{n}{di}\bigg\rfloor\right)\left(\sum_{j = 1}^{\lfloor\frac{m}{d}\rfloor}\bigg\lfloor\frac{m}{dj}\bigg\rfloor\right) \end{aligned} \]设 \(S(n) = \sum\limits_{i = 1}^{n}\lfloor\frac{n}{i}\rfloor\)，则原式可替换为：
\[\sum_{d = 1}^n\mu(d)S\left(\bigg\lfloor\frac{n}{d}\bigg\rfloor\right)S\left(\bigg\lfloor\frac{m}{d}\bigg\rfloor\right) \]预处理一下 \(\mu(n)\) 的前缀和与 \(S(n)\) 的值，进行数论分块即可。
参考代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e4 + 10;
int cnt, st[N], primes[N];
int n, m;
ll S[N], mu[N];
void init()
{
mu[1] = 1;
for (ll i = 2; i < N; i ++ )
{
if (!st[i]) primes[cnt ++ ] = i, mu[i] = -1;
for (int j = 0; primes[j] * i < N; j ++ )
{
st[primes[j] * i] = 1;
if (i % primes[j] == 0) break;
mu[primes[j] * i] = -mu[i];
}
}
for (int i = 1; i < N; i ++ )
{
mu[i] += mu[i - 1];
for (int l = 1, r; l <= i; l = r + 1)
{
r = i / (i / l);
S[i] += 1ll * (r - l + 1) * (i / l);
}
}
}
ll calc(int n, int m)
{
ll res = 0;
for (int l = 1, r; l <= min(n, m); l = r + 1)
{
r = min(n / (n / l), m / (m / l));
res += (mu[r] - mu[l - 1]) * S[n / l] * S[m / l];
}
return res;
}
void solve()
{
scanf("%d%d", &n, &m);
printf("%lld\n", calc(n, m));
}
int main()
{
init();
int T;
scanf("%d", &T);
while (T -- ) solve();
return 0;
}