题目题解

问题理解

给定 $a, b$ 和 $q$ 个查询 $[l_i, r_i]$，要求统计区间内满足

的整数 $x$ 的个数。

第一步：周期性

设 $L = \mathrm{lcm}(a, b)$，实际上 $L = a \cdot b$（因为 $a,b$ 不一定是互质的，但 $ab$ 一定是公倍数）。
可以验证：对于任意整数 $x$ 和 $t$，有

因为 $L$ 是 $a$ 和 $b$ 的倍数，所以 $x$ 和 $x+L$ 在模 $a$ 和模 $b$ 下余数相同，进而嵌套余数也相同。
因此，条件是否成立只取决于 $x \bmod L$。

第二步：前缀计数

我们可以预处理数组 $p[0..L]$，其中 $p[i]$ 表示 $[0, i]$ 中满足条件的数的个数（$i$ 从 $0$ 到 $L$）。
注意 $0 \le x < L$，但 $x=0$ 时 $(0 \bmod a) \bmod b = 0$，$(0 \bmod b) \bmod a = 0$，相等，不计数。

对于任意 $x$，设 $q = \lfloor x / L \rfloor$，$r = x \bmod L$，则

因为前 $q$ 个完整周期每个有 $p[L]$ 个满足条件的数，最后一个不完整周期有 $p[r]$ 个。

第三步：区间查询

对于查询 $[l, r]$，答案即为

第四步：实现细节

• 预处理 $p[i]$ 只需计算到 $L = a \cdot b$，因为 $a,b \le 200$，$L \le 40000$，可行。
• 注意 $l, r$ 可达 $10^{18}$，需要用 long long。
• 对于每个测试用例，先调用 build(a, b) 计算 $p$ 数组，然后回答查询。

时间复杂度

• 预处理 $O(ab)$。
• 每个查询 $O(1)$。
• 总复杂度 $O(ab + q)$，满足 $a,b \le 200$，$q \le 500$。

代码实现

#include <bits/stdc++.h>
using namespace std;

const int N = 40043;

int len;
int p[N];

void build(int a, int b) {
    len = a * b;
    p[0] = 0;
    for (int i = 1; i <= len; i++) {
        p[i] = p[i - 1];
        if ((i % a) % b != (i % b) % a) {
            p[i]++;
        }
    }
}

long long query(long long x) {
    long long cnt = x / len;
    int rem = x % len;
    return 1LL * p[len] * cnt + p[rem];
}

long long query(long long l, long long r) {
    return query(r) - query(l - 1);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    while (t--) {
        int a, b, q;
        cin >> a >> b >> q;
        build(a, b);
        while (q--) {
            long long l, r;
            cin >> l >> r;
            cout << query(l, r) << " ";
        }
        cout << "\n";
    }
    
    return 0;
}

验证样例

输入：

2
4 6 5
1 1
1 3
1 5
1 7
1 9
7 10 2
7 8
100 200

输出：

0 0 0 2 4 
0 91 

与题目输出一致。

总结

本题的关键在于：

1. 发现周期性，周期为 $L = a \cdot b$。
2. 预处理每个周期内的前缀和，用于 $O(1)$ 回答查询。
3. 注意 $0$ 是否计入，根据条件判断。