[题解] SDOI2015 约数个数和

Table of Contents

题目描述

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

输入格式

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

输出格式

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

样例输入

2
7 4
5 6

样例输出

110
121

数据范围及约束

$T, N, M \leq 50 000$

解题思路

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

证明
$d (i j) = \sum_{p ∣ i} \sum_{q ∣ j} [g c d (p, q) = 1]$

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

而 $\sum_{p ∣ i} \sum_{q ∣ j} [g c d (p, q) = 1] $ 中有

$p $ 取 $k^{0} $ ， $q $ 取 $k^{0}, k^{1}, k^{2}, \dots, k^{b} $ 共 $b + 1 $ 种
$p $ 取 $k^{0}, k^{1}, k^{2}, \dots, 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}, \dots, y_{i} \times k^{b}$ 共 $S \times (b + 1)$ 种
$p $ 取 $x_{i} \times k^{0}, x_{i} \times k^{1}, \dots, 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;
}