[题解] SDOI2015 约数个数和

Wong, LimstashOI, 数学, 莫比乌斯反演

题目描述

设 $d(x)$ 为 $x$ 的余数个数，给定 $N$ 和 $M$，求 $\sum_{i=1}^N \sum_{j=1}^M d(ij)$

输入格式

输入文件包含多组测试数据。第一行，一个整数 $T$，表示测试数据的组数。接下来的 $T$ 行，每行两个整数 $N, M$。

输出格式

$T​$ 行，每行一个整数，表示你所求的答案。

样例输入

2
7 4
5 6

样例输出

110
121

数据范围及约束

$T, N, M\leq 50\ 000$

解题思路

首先我们要知道 $d(ij) = \sum_{p \mid i} \sum_{q \mid j} [\gcd([p, q]) = 1] $，这个在之后给出了证明
$$
\begin{aligned}
& \sum_{i=1}^n \sum_{j=1}^m d(ij) \\
= & \sum_{i=1}^n \sum_{j=1}^m \sum_{p \mid i} \sum_{q \mid j} [\gcd(p, q) = 1] \\
= & \sum_{p=1}^n \sum_{q=1}^m \sum_{i=1}^n \sum_{j=1}^m [p \mid i] [q \mid j] [\gcd(p, q) = 1] \\
= & \sum_{p=1}^n \sum_{q=1}^m \lfloor \frac{n}{p} \rfloor \lfloor \frac{m}{q} \rfloor [gcd(p, q) = 1] \\
= & \sum_{p=1}^n \sum_{q=1}^m \lfloor \frac{n}{p} \rfloor \lfloor \frac{m}{q} \rfloor \sum_{k \mid p} \sum_{k \mid q} \mu(k) \\
= & \sum_{k=1}^{\min(i, j)} \mu(k) \sum_{p=1}^n \sum_{q=1}^m \lfloor \frac{n}{p} \rfloor \lfloor \frac{m}{q} \rfloor[k \mid p] [k \mid q]\\
= & \sum_{k=1}^{\min(i, j)} \mu(k) \sum_{p=1}^{n/k} \sum_{q=1}^{m/k} \lfloor \frac{n}{pk} \rfloor \lfloor \frac{m}{qk} \rfloor
\end{aligned}
$$
可以先预处理出 $\sum_{i=1}^n \lfloor \frac{n}{i} \rfloor$ 在 $1, 2, \cdots, 50 \ 000$ 处的答案，然后可以 $O(1)$ 询问后半部分的答案，再套用整除分块，在 $O(\sqrt{n})$ 的时间内做出单组询问

证明
$$
d(ij) = \sum_{p \mid i} \sum_{q \mid j} [gcd(p, q) = 1]
$$

对于一个 $i​$ 和 $j​$ 中只含 $k​$ 这个质因子，假设 $i​$ 中含有 $a​$ 个，$j​$ 中含有 $b​$ 个，那么 $i \times j​$ 就有 $a + b + 1​$ 个约数

而 $\sum_{p \mid i} \sum_{q \mid j} [gcd(p, q) = 1] ​$ 中有

  • $p​$ 取 $k^0​$，$q​$ 取 $k^0, k^1, k^2, \cdots, k^b​$ 共 $b+1​$ 种
  • $p​$ 取 $k^0, k^1, k^2, \cdots, k^a​$ ，$q​$ 取 $k^0​$ 共 $a+1​$ 种
  • 上面两种情况中重复计算了 $p​$ 取 $k^0​$ 且 ​$q​$ 取 ​$k^0​$ 的情况，减去 ​$1​$ 种

因此对于只含有单一质因子的情况，这个式子是成立的

假设对于含有前 $n$ 个 $(n \geq 1)$ 质因子的情况成立，即 $i = \prod_{s=1}^n k_s^{a_s}$，$j = \prod_{s=1}^n k_s^{b_s}$ 已经成立，共有 $\prod_{s=1}^{n} (a_s + b_s) + 1$ 个约数，记为 $S$

考虑假如第 $n+1​$ 个质因子，之前已经有 $S​$ 个两两互质的二元组 $<x_i, y_i>​$，第 $n+1​$ 个因数 $p​$ 中有 $a​$ 个，$q​$ 中有 $b​$ 个

  • $p$ 取 $x_i \times k^0$ ，$q$ 取 $y_i \times k^0, y_i \times k^1, \cdots, y_i \times k^b$ 共 $S \times (b+1)$ 种
  • $p​$ 取 $x_i \times k^0, x_i \times k^1, \cdots, x_i \times k^a​$ ，$q​$ 取 $y_i \times k^0​$ 共 $S \times (a+1)​$ 种
  • 上面两种情况重复计算了 $p​$ 取 $x_i \times k^0​$ 且 $q​$ 取 $y_i \times k^0​$ 的情况，共 $S​$ 种

总共有 $S \times (a+b+1)​$ 种，由归纳法证明成立

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>

using namespace std;
const int MAXN = 50000 + 10;
const int SIZ = 50000;

int pri[MAXN], cnt;
long long sum[MAXN], num[MAXN], mu[MAXN];
bool isNotPrime[MAXN];

inline void init() {
    mu[1] = 1;

    for (register int i=2; i<=SIZ; i++) {
        if (!isNotPrime[i]) {
            mu[i] = -1;
            pri[++cnt] = i;
        }

        for (register int j=1; j<=cnt; j++) {
            int m = i * pri[j];
            if (m > SIZ) break;
            isNotPrime[m] = true;

            if (i % pri[j] == 0) {
                mu[m] = 0;
                break;
            } else {
                mu[m] = -mu[i];
            }
        }
    }

    for (register int i=1; i<=SIZ; i++) {
        sum[i] = sum[i-1] + mu[i];
    }

    for (register int i=1; i<=SIZ; i++) {
        int r = 0;
        long long res = 0;

        for (register int l = 1; l <= i; l = r + 1) {
            r = i / (i / l);
            res += (r - l + 1) * (i / l);
        }

        num[i] = res;
    }
}

inline long long solve(int n, int m) {
    int r = 0;
    long long res = 0;

    for (register int l=1; l <= min(n, m); l = r + 1){
        r = min(n / (n / l), m / (m / l));
        res += (sum[r] - sum[l-1]) * num[n / l] * num[m / l];
    }

    return res;
}

int T, n, m;

int main(){
    init();
    scanf("%d", &T);

    for (register int i=1; i<=T; i++) {
        scanf("%d%d", &n, &m);
        printf("%lld\n", solve(n, m));
    }

    return 0;
}