题目链接

转载自 walker

前置知识

  • 假设 能唯一分解为 ，莫比乌斯函数 定义为：

是偶数是奇数或其他

题目分析

给定 ，求满足 ，并且 的数对 个数 等价于 求满足 ，，并且 的数对 个数，即求两个区间内有多少对这样的数对是互质的。

证明：假设 ，那么 ，矛盾。

可以用容斥原理求解，设 ， ，接下来统计不合法的对数：

有一个质公因子的方案数量：

有两个质公因子的方案数量：

有三个质公因子的方案数量：

所以根据容斥原理，合法方案数为：

只含一个质公因子只含两个质公因子只含三个质公因子

注意到符号项就是莫比乌斯函数，故合法方案数可用莫比乌斯函数表示：

注意， 中因子 的个数就是 个，不仅只有质因子有这样的性质

如果直接枚举 ，由于 ，复杂度是 级别，并且询问个数有 ，直接枚举是 级别，考虑优化。

我们发现，这个式子理论上 最多需要枚举 次，但实际上因为整除的缘故，有很多 对应的 和 都是相同的，所以是冗余枚举。由于 从小到大枚举， 都是单调递减的，并且理论上只有 个不同的值（ 同样）。这里用到了 AcWing 199. 余数之和 中的知识。

分块证明：

分段讨论：

  • 当 时，因为 是 中的整数，所以只有 个不同的 值。
  • 当 时，，又因为式子取整了，所以式子只能取到 的值，故最多也只有 个不同的 值。

有关当 时， 的证明：

由于下取整，所以 ，假设 ，那么 ，矛盾。

图和证明引自：墨染空

我们现在已经证明出了，可以将一段 长度为 的序列分成 段的序列，如果我们能做到 处理每一段，那么就可以将原先 的复杂度优化至 。

假设有 ，假设此时的 是下界，求能使这个值不变的，最大的 为多少（上界），记这个上界是 。举个例子，，值为 ，其中 是下界，那么上界就是 ，因为 。所以有 ，且 。这里的 实际上是有公式的：

公式证明：

我们要证明的是 ，且 ，只有满足这个条件，才能证明 是使这个值不变的上界。

由于：

故 ，所以 。又因为

所以 ，第一部分证毕。

用带余除法证明第二部分：

设 ， 则 ，并且用第一部分证得的结论，代入第二部分式子得：

所以等价于证明

等价于证明

再令 ，则 ，等价于证明：

由于 ，因此得证。

代码实现

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
64
65
66
// Author: CodeBoy

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define Re register
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) > (b) ? (b) : (a))
using namespace std;
typedef long long ll;
const int N = 50010;

int primes[N], cnt;
bool st[N];
int mobius[N], sum[N];

void init(int n)
{
    mobius[1] = 1;
    for (int i = 2; i <= n; i++)
    {
        if (!st[i])
        {
            primes[cnt++] = i;
            mobius[i] = -1;
        }
        for (int j = 0; primes[j] * i <= n; j++)
        {
            int t = primes[j] * i;
            st[t] = true;
            if (i % primes[j] == 0)
            {
                mobius[t] = 0;
                break;
            }
            mobius[t] = mobius[i] * -1;
        }
    }

    for (int i = 1; i <= n; i++)
        sum[i] = sum[i - 1] + mobius[i];
}

int main()
{
    init(N - 1);
    int t;
    scanf("%d", &t);
    while (t--)
    {
        int a, b, d;
        scanf("%d%d%d", &a, &b, &d);
        a /= d, b /= d;
        int n = min(a, b);
        ll res = 0;
        for (int l = 1, r; l <= n; l = r + 1)
        {
            r = min(n, min(a / (a / l), b / (b / l)));
            res += (sum[r] - sum[l - 1]) * (ll)(a / l) * (b / l);
        }
        printf("%lld\n", res);
    }

    return 0;
}