CF1342C

FiraCode · 2022-07-27 10:15:37 · 题解

题解思路：

我们就设 a>b。

那么当 x<a，那么 x \bmod a 就是无效操作。

而 x \bmod b + \bmod a 中 \bmod a 也是无效的。

那么 x \bmod b = x \bmod b \bmod a

那么 a 和 b 的 \operatorname{lcm}，若 x \bmod\operatorname{lcm} = 0。

那么就相当于 x \bmod a = 0 并且 x \bmod b = 0。

当 x = \operatorname{lcm} + 1。

那么 x \bmod a = 1,x \bmod b = 1。

当 x = \operatorname{lcm} + a - 1。

那么 x \bmod a = a - 1,x \bmod b = x \bmod a - 1。

那么一般情况 x = [k \cdot \operatorname{lcm} ~ k \cdot \operatorname{lcm} + a - 1] 里的 x\mod a 和 x\mod b 是相同的，否则就是不同的。

那么对于一个区间 [l,r] 我们要看这里面有多少个 \operatorname{lcm}，那么我们就用前缀。

那么就是 (sum_{r \div \operatorname{lcm}} - sum_{l \div \operatorname{lcm}}) \times (\operatorname{lcm} - a)。

但我们少加了一些值，那么我们要再加上 r \bmod \operatorname{lcm} - a + 1。

但 l 这部分多加了，所以我们要减去 l \bmod \operatorname{lcm} - a。

AC CODE：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int T;
int main()
{
    scanf("%d", &T);
    while (T--)
    {
        ll a, b, q;
        cin >> a >> b >> q;
        if (a < b)
            swap(a, b);
        ll lcm = a * b / __gcd(a, b);
        ll len = lcm - a;
        while (q--)
        {
            ll ans = 0;
            ll l, r;
            cin >> l >> r;
            ll x = r / lcm - l / lcm;
            ans += x * len;
            r %= lcm;
            if (r >= a)
                ans += r - a + 1;
            l %= lcm;
            if (l > a)
                ans -= l - a;
            cout << ans << ' ';
        }
        puts("");
    }
    return 0;
}