主要思路

自己推了三个假的循环，遂奔向题解。

先考虑设循环节为 \(k\)，且考虑最终 \(x = 0, y = 0\) 的局势。我们考虑怎样的循环节才能迭代一次、得到同样的 \(x = 0, y = 0\) 的局势。不妨直接带入 \(k\)：

\[ x = (k + \lfloor \frac{k}{B} \rfloor) \bmod A, y = k \bmod B \]

此时终局势为 \(x = 0, y = 0\)，那么可以得到信息 \(B | k\)。此时下取整已经没有效益，得：

\[ \begin{aligned} k + \frac{k}{B} &\equiv 0 \pmod A \\ k(B + 1) &\equiv 0 \pmod A \end{aligned} \]

算完这玩意之后，我们可以突破模意义的限制得到：

\[ \begin{aligned} k(B + 1) &= Ai \\ k &= i \cdot \frac{A}{B + 1} \end{aligned} \]

由于 \(k\) 是个整数，则 \(i\) 需要满足：

\[ i = j \frac{B + 1}{\gcd(A, B + 1)} \]

再加上 \(B | k\) 的条件，很容易得到：

\[ i = j B \frac{B + 1}{\gcd(A, B + 1)} \]

那么循环节就是：

\[ \begin{aligned} k &= j B \frac{B + 1}{\gcd(A, B + 1)} \cdot \frac{A}{B + 1} \\ &= j \frac{AB}{\gcd(A, B + 1)} \\ k &\equiv 0 \pmod {\frac{AB}{\gcd(A, B + 1)}} \end{aligned} \]

代码

// LOJ3144.cpp
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAX_N = 1e6 + 200;

ll n, A, B, loop, cnt;
pair<ll, ll> segs[MAX_N << 1];

ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a % b); }

int main()
{
    scanf("%lld%lld%lld", &n, &A, &B);
    loop = A / gcd(A, B + 1) * B;
    for (int i = 1; i <= n; i++)
    {
        ll l, r;
        scanf("%lld%lld", &l, &r);
        if (r - l + 1 >= loop)
            printf("%lld\n", loop), exit(0);
        l %= loop, r %= loop;
        if (l <= r)
            segs[++cnt] = make_pair(l, r);
        else
            segs[++cnt] = make_pair(l, loop - 1), segs[++cnt] = make_pair(0, r);
    }
    sort(segs + 1, segs + 1 + cnt);
    segs[++cnt] = make_pair(loop + 1, 0);
    ll lft = segs[1].first, rig = segs[1].second, ans = 0;
    for (int i = 2; i <= cnt; i++)
    {
        if (rig < segs[i].first)
        {
            ans += rig - lft + 1;
            lft = segs[i].first, rig = segs[i].second;
        }
        else
            rig = max(rig, segs[i].second);
    }
    printf("%lld\n", ans);
    return 0;
}