「题目描述」
设 $d(x)$ 为 $x$ 的约数个数，给定 $n, m$ ，求： $$ \sum_{i = 1}^n \sum_{j = 1}^m d(ij) $$ $n, m \leq 50000$ ，$T$ 组询问，$T \leq 50000$ 。
「题目链接」
BZOJ 3994 约数个数和 「SDOI 2015」
「解题思路」
首先我们有这样的一个结论：
$$ d(ij) = \sum_{r \mid i} \sum_{s \mid j} [(r, s) = 1] $$
分解，设 $ij = \prod p_k^{c_k}$ ，则 $d(ij) = \prod (c_k + 1)$ ，这是约数个数的一般公式。
下面说明等式右边能给出同样的结果。
设 $i = \prod p_k^{a_k}$ ，$j = \prod p_k^{b_k}$ ，应有 $a_k + b_k = c_k$ 。
那么我们考虑 $r = \prod p_k^{x_k}, s = \prod p_k^{y_k}$ ，欲使 $(r, s) = 1$ ，对所有的 $k$ ，都应满足 $x_k = 0$ 或 $y_k = 0$。
然后考虑对于每个 $k$ ，满足该条件的 $x_k, y_k$ 组合方式有多少。
当 $x_k = 0, y_k = 0$ 时，仅有 1 种 。
当 $x_k \not = 0, y_k = 0$ 时，$x_k$ 可以取 $1 \dots a_k$ ，共 $a_k$ 种。
当 $x_k = 0, y_k \not = 0$ 时，$y_k$ 可以取 $1 \dots b_k$ ，共 $b_k$ 种。
所以每个 $k$ 有 $a_k + b_k + 1 = c_k + 1$ 种，再根据乘法原理，给出 $d(i, j) = \prod (c_k + 1)$ ，证毕。
得到这个结论后，我们从其出发，推导一番： $$ \begin{align*} d(i, j) &= \sum_{r \mid i} \sum_{s \mid j} [(r, s) = 1] \newline &= \sum_{r \mid i} \sum_{s \mid j} \sum_{x \mid (r, s)} \mu(x) \newline &= \sum_{x} \mu(x) \sum_{r \mid i} \sum_{s \mid j} [x \mid (r, s)] \newline &= \sum_{x} \mu(x) \sum_{r \mid i} \sum_{s \mid j} [x \mid r \land x \mid s] \newline &= \sum_{x} \mu(x) \sum_{r \mid i} \sum_{s \mid j} [x \mid r][x \mid s] \newline &= \sum_{x} \mu(x) \sum_{r \mid i} [x \mid r] \sum_{s \mid j} [x \mid s] \end{align*} $$ 我们将指出： $$ \sum_{r \mid i} [x \mid r] = d(\frac i x) [x \mid i] $$ 这是求满足 $x \mid r, r \mid i$ 的 $r$ 的个数，为了保证 $x \mid r$ ，干脆设 $r = tx$ ，那么就是求使 $tx \mid i$ 的 $t$ 的个数，首先必须要有 $x \mid i$ ，然后就是使 $t \mid \frac i x$ 的 $t$ 的个数，也就是 $d(\frac i x)$ 咯。
综上，我们有： $$ d(ij) = \sum_{x} \mu(x) d(\frac i x)[x \mid i] d(\frac j x) [x \mid j] $$ 考虑答案： $$ \begin{align*} \sum_{i = 1}^n \sum_{j = 1}^m d(ij) &= \sum_{i = 1}^n \sum_{j = 1}^m \sum_{x} \mu(x) d(\frac i x) [x \mid i] d(\frac j x) [x \mid j] \newline &= \sum_{x} \mu(x) \sum_{i = 1}^n d(\frac i x) [x \mid i] \sum_{j = 1}^m d(\frac j x) [x \mid j] \newline &= \sum_{x} \mu(x) \sum_{i' = 1}^{\left \lfloor \frac n x \right \rfloor} d(i') \sum_{j' = 1}^{\left \lfloor \frac m x \right \rfloor} d(j') \end{align*} $$ $d$ 是积性函数，可以线性筛 $O(n)$ 预处理。
然后成块统计答案，就可以做到单次询问 $O(\sqrt n)$ 了。
「AC 代码」
#include <cstdio>
#include <algorithm>
typedef long long int64;
const int MAX_N = 50000;
bool isNotPrime[MAX_N + 1];
int min[MAX_N + 1], cnt[MAX_N + 1];
int primes[MAX_N], m;
int64 mu[MAX_N + 1], d[MAX_N + 1];
inline void sieve(int n = MAX_N){
isNotPrime[1] = true, min[1] = 0, cnt[1] = 1, mu[1] = 1, d[1] = 1;
for(int i = 2; i <= n; i++){
if(!isNotPrime[i]){
primes[m++] = i;
min[i] = i, cnt[i] = 1;
mu[i] = -1, d[i] = 2;
}
for(int j = 0, p, x; j < m; j++){
if((x = i * (p = primes[j])) > n) break;
isNotPrime[x] = true;
if(i % p == 0) min[x] = min[i] * p, cnt[x] = cnt[i] + 1; else min[x] = p, cnt[x] = 1;
if(x == min[x]){
mu[x] = 0;
d[x] = cnt[x] + 1;
} else{
mu[x] = mu[ min[x] ] * mu[ x / min[x] ];
d[x] = d[ min[x] ] * d[ x / min[x] ];
}
if(i % p == 0) break;
}
}
for(int i = 1; i <= n; i++) mu[i] += mu[i - 1], d[i] += d[i - 1];
}
inline int64 solve(int n, int m){
if(n > m) std::swap(n, m);
int64 ans = 0;
for(int l = 1, r; l <= n; l = r + 1){
r = std::min(n / (n / l), m / (m / l));
ans += (mu[r] - mu[l - 1]) * d[n / l] * d[m / l];
}
return ans;
}
int main(){
sieve();
int T;
scanf("%d", &T);
for(int i = 0, n, m; i < T; i++){
scanf("%d%d", &n, &m);
printf("%lld\n", solve(n, m));
}
return 0;
}
就是这样咯～