「SDOI2015」约数个数和 题解

题目大意

设 $d(x)$ 为 $x$ 的约数个数，给定 $N, M$，求：

$$\sum_{i=1}^N \sum_{j=1}^M d(ij)$$

多组测试数据，$T \leq 50000$，$N, M \leq 50000$。

关键结论

有一个重要公式：

$$d(ij) = \sum_{x|i} \sum_{y|j} [\gcd(x, y) = 1]$$

其中 $[P]$ 在 $P$ 为真时值为 $1$，否则为 $0$。

推导过程

第一步：代入公式

$$\begin{aligned} S &= \sum_{i=1}^N \sum_{j=1}^M d(ij) \\ &= \sum_{i=1}^N \sum_{j=1}^M \sum_{x|i} \sum_{y|j} [\gcd(x, y) = 1] \end{aligned} $$

第二步：交换求和顺序

先枚举 $x, y$：

$$S = \sum_{x=1}^N \sum_{y=1}^M [\gcd(x, y) = 1] \cdot \left\lfloor \frac{N}{x} \right\rfloor \cdot \left\lfloor \frac{M}{y} \right\rfloor $$

第三步：莫比乌斯反演

设：

$$f(t) = \sum_{x=1}^N \sum_{y=1}^M [\gcd(x, y) = t] \cdot \left\lfloor \frac{N}{x} \right\rfloor \cdot \left\lfloor \frac{M}{y} \right\rfloor $$

我们要求 $f(1)$。

设：

$$F(t) = \sum_{t|d} f(d) = \sum_{x=1}^N \sum_{y=1}^M [t|\gcd(x, y)] \cdot \left\lfloor \frac{N}{x} \right\rfloor \cdot \left\lfloor \frac{M}{y} \right\rfloor $$

令 $x = tx', y = ty'$，则：

$$F(t) = \sum_{x'=1}^{\lfloor N/t \rfloor} \sum_{y'=1}^{\lfloor M/t \rfloor} \left\lfloor \frac{N}{tx'} \right\rfloor \cdot \left\lfloor \frac{M}{ty'} \right\rfloor $$

第四步：定义辅助函数

定义：

$$g(n) = \sum_{k=1}^n \left\lfloor \frac{n}{k} \right\rfloor = \sum_{k=1}^n d(k) $$

则：

$$F(t) = g\left( \left\lfloor \frac{N}{t} \right\rfloor \right) \cdot g\left( \left\lfloor \frac{M}{t} \right\rfloor \right) $$

第五步：反演得到答案

由莫比乌斯反演：

$$f(1) = \sum_{d=1}^{\min(N,M)} \mu(d) F(d) = \sum_{d=1}^{\min(N,M)} \mu(d) \cdot g\left( \left\lfloor \frac{N}{d} \right\rfloor \right) \cdot g\left( \left\lfloor \frac{M}{d} \right\rfloor \right) $$

算法步骤

1. 预处理：

   • 线性筛求出 $\mu(n)$ 和 $d(n)$（约数个数）
   • 计算 $g(n) = \sum_{k=1}^n d(k)$ 的前缀和
   • 计算 $\mu(n)$ 的前缀和

2. 查询处理：

   • 对于每组 $N, M$，使用整除分块计算：$$\sum_{d=1}^{\min(N,M)} \mu(d) \cdot g\left( \left\lfloor \frac{N}{d} \right\rfloor \right) \cdot g\left( \left\lfloor \frac{M}{d} \right\rfloor \right) $$

复杂度分析

• 预处理：$O(N)$
• 单次查询：$O(\sqrt{N})$
• 总复杂度：$O(N + T\sqrt{N})$，可以通过

代码实现

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

typedef long long ll;

const int MAXN = 50000;

int mu[MAXN+5], prime[MAXN+5], cnt;
bool vis[MAXN+5];
int d[MAXN+5], minp[MAXN+5];
ll g[MAXN+5];

void sieve() {
    mu[1] = 1;
    d[1] = 1;
    for (int i = 2; i <= MAXN; i++) {
        if (!vis[i]) {
            prime[++cnt] = i;
            mu[i] = -1;
            d[i] = 2;
            minp[i] = 1;
        }
        for (int j = 1; j <= cnt && i * prime[j] <= MAXN; j++) {
            vis[i * prime[j]] = true;
            if (i % prime[j] == 0) {
                mu[i * prime[j]] = 0;
                minp[i * prime[j]] = minp[i] + 1;
                d[i * prime[j]] = d[i] / (minp[i] + 1) * (minp[i] + 2);
                break;
            } else {
                mu[i * prime[j]] = -mu[i];
                d[i * prime[j]] = d[i] * 2;
                minp[i * prime[j]] = 1;
            }
        }
    }
    
    for (int i = 1; i <= MAXN; i++) {
        mu[i] += mu[i-1];
        g[i] = g[i-1] + d[i];
    }
}

int main() {
    sieve();
    int T;
    scanf("%d", &T);
    while (T--) {
        int N, M;
        scanf("%d%d", &N, &M);
        if (N > M) swap(N, M);
        ll ans = 0;
        for (int l = 1, r; l <= N; l = r + 1) {
            r = min(N / (N / l), M / (M / l));
            ans += (ll)(mu[r] - mu[l-1]) * g[N/l] * g[M/l];
        }
        printf("%lld\n", ans);
    }
    return 0;
}

总结

本题的关键在于利用 $d(ij)$ 的分解公式和莫比乌斯反演，将双重求和转化为可整除分块的形式，从而将单次查询复杂度优化到 $O(\sqrt{N})$，能够处理大规模数据。