本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 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;
}