「HAOI2011」Problem b - 莫比乌斯反演

发表于 更新于 分类于 ， 阅读次数： Disqus：

题意描述

洛谷链接

对于给出的 \(n\) 个询问，每次求有多少个数对 \((x,y)\)，满足 \(a \le x \le b\)，\(c \le y \le d\)，且 \(\gcd(x,y) = k\)，\(\gcd(x,y)\) 函数为 \(x\) 和 \(y\) 的最大公约数。

对于 \(100\%\) 的数据满足：\(1 \le n,k \le 5 \times 10^4\)，\(1 \le a \le b \le 5 \times 10^4\)，\(1 \le c \le d \le 5 \times 10^4\)。

解题思路

本题要求以下式子的值：

\[ \sum_{x = a}^b{ \sum_{y = c}^d{ [\gcd(x, y) = k] } } \]

看到单元函数我们可以想到尝试用莫比乌斯反演化简。

首先我们设函数 \(A(n, m, k) = \sum_{i = 1}^n{ \sum_{j = 1}^m{ [\gcd(i, j) = k] } }\)，由容斥原理易得答案为 \(A(b, d, k) - A(a - 1, d, k) - A(b, c - 1, k) + A(a - 1, c - 1, k)\)。

于是我们只需求出 \(A(n, m, k)\) 的值即可。设以下函数：

\[ f(k) = \sum_{i = 1}^n{ \sum_{j = 1}^m{ [\gcd(i, j) = k] } } \]

\[ F(d) = \sum_{d | k}{f(k)} \]

我们可以将函数 \(F(d)\) 进行化简：

\[ \begin{align*} F(d) &= \sum_{d | k}{f(k)} \\ &= \sum_{d | k}{ \sum_{i = 1}^n{ \sum_{j = 1}^m{ [\gcd(i, j) = k] } } } \\ &= \sum_{t = 1}^{ \min\{ \lfloor \frac{n}{d} \rfloor , \lfloor \frac{m}{d} \rfloor \} }{ \sum_{i = 1}^n{ \sum_{j = 1}^m{ [\gcd(i, j) = td] } } } \\ &= \sum_{i = 1}^n{ \sum_{j = 1}^m{ [d | \gcd(i, j)] } } \\ &= \sum_{i = 1}^n{ \sum_{j = 1}^m{ [d | i][d | j] } } \\ &= \lfloor \frac{n}{d} \rfloor \lfloor \frac{m}{d} \rfloor \end{align*} \]

又由于 \(F(d) = \sum_{d | k}{f(k)}\)，我们可以进行莫比乌斯反演：

\[ f(k) = \sum_{k | d}{\mu(\frac{d}{k})F(d)} \]

然后接着进行化简：

\[ \begin{align*} f(k) &= \sum_{k | d}{\mu(\frac{d}{k})F(d)} \\ &= \sum_{k | d}{\mu(\frac{d}{k}) \lfloor \frac{n}{d} \rfloor \lfloor \frac{m}{d} \rfloor } \\ &= \sum_{t = 1}^{ \min\{ \lfloor \frac{n}{k} \rfloor , \lfloor \frac{m}{k} \rfloor \} }{\mu(t) \lfloor \frac{n}{tk} \rfloor \lfloor \frac{m}{tk} \rfloor } \end{align*} \]

于是我们可以得出：

\[ A(n, m, k) = \sum_{t = 1}^{ \min\{ \lfloor \frac{n}{k} \rfloor , \lfloor \frac{m}{k} \rfloor \} }{\mu(t) \lfloor \frac{n}{tk} \rfloor \lfloor \frac{m}{tk} \rfloor } \]

此时对于单词询问的时间复杂度为 \(O(n)\)，直接运行 \(A(n, m, k)\) 会 TLE，故我们还要进行进一步的优化。

我们可以发现在 \(A(n, m, k)\) 中大量出现 \(\lfloor \frac{n}{k} \rfloor\) 与 \(\lfloor \frac{m}{k} \rfloor\)，于是我们可以考虑将其提前计算。

我们定义以下函数：

\[ n' = \lfloor \frac{n}{k} \rfloor, m' = \lfloor \frac{m}{k} \rfloor \]

\[ A'(n', m') = A(n, m, k) = \sum_{t = 1}^{ \min\{n', m'\} }{\mu(t) \lfloor \frac{n'}{t} \rfloor \lfloor \frac{m'}{t} \rfloor } \]

对于 \(A'(n', m')\)，我们可以先统计出 \(\mu(t)\) 的前缀和，再用数论分块求解。这时候的单词询问时间复杂度优化到了 \(O(\sqrt{n})\)，可过此题。

代码演示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <cstdio>
#include <iostream>

const int MAXN = 5e4;

bool isNotPrime[MAXN + 1];
int mu[MAXN + 1], primes[MAXN + 1], cnt;
int sumMu[MAXN + 1];

inline void getPrimes() {
    isNotPrime[0] = isNotPrime[1] = true;
    mu[1] = 1;
    for (int i = 2; i <= MAXN; i++) {
        if (!isNotPrime[i]) {
            primes[++cnt] = i;
            mu[i] = -1;
        }

        for (int j = 1; j <= cnt; j++) {
            int t = i * primes[j];
            if (t > MAXN) break;

            isNotPrime[t] = true;

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

    sumMu[0] = 0;
    for (int i = 1; i <= MAXN; i++) sumMu[i] = sumMu[i - 1] + mu[i];
}

int f(int n, int m, int k) {
    int ans = 0;

    n /= k, m /= k;
    for (int l = 1, r; l <= std::min(n, m); l = r + 1) {
        r = std::min(n / (n / l), m / (m / l));
        ans += (sumMu[r] - sumMu[l - 1]) * ((n / l) * (m / l));
    }

    return ans;
}

int main() {
    getPrimes();

    int t;

    scanf("%d", &t);

    while (t--) {
        int a, b, c, d, k;
        scanf("%d %d %d %d %d", &a, &b, &c, &d, &k);

        printf("%d\n", f(b, d, k) - f(a - 1, d, k) - f(b, c - 1, k) + f(a - 1, c - 1, k));
    }

    return 0;
}