Given two arithmetic progressions $A_i = a_1 i + b_1$ and $B_i = a_2 i + b_2$ for $i \in \mathbb{N}$, and integers $l \leq r$, determine how many integers $n \in [l, r]$ appear in both sequences.

We seek integer solutions $(x, y) \in \mathbb{N}^2$ to the equation: $$ a_1 x + b_1 = a_2 y + b_2 $$ Rewriting gives the linear Diophantine equation: $$ a_1 x - a_2 y = b_2 - b_1 $$ Let $g = \gcd(a_1, a_2)$. If $(b_2 - b_1)$ is not divisible by $g$, there are no common terms, and the answer is 0.

Otherwise, use the extended Euclidean algorithm to find a particular solution $(x_0, y_0)$. The genarel solution is: $$ x = x_0 + k \cdot \frac{a_2}{g}, \quad y = y_0 + k \cdot \frac{a_1}{g}, \quad k \in \mathbb{Z} $$ To ensure $x, y \geq 0$, adjust $k$ sothat both coordinates are minimized but non-negative. This yields the smallest valid base solution $(x_{\min}, y_{\min})$ with $k = 0$.

The corresponding common term is: $$ n = a_1 x_{\min} + b_1 $$ and subsequent common terms increase by $L = \mathrm{lcm}(a_1, a_2) = \frac{a_1 a_2}{g}$.

Thus, all common terms form an arithmetic progression starting at $n_0 = a_1 x_{\min} + b_1$ with step $L$. We now count how many terms of this new progression fall within $[l, r]$.

Let: $$ k_{\min} = \left\lceil \frac{l - n_0}{L} \right\rceil, \quad k_{\max} = \left\lfloor \frac{r - n_0}{L} \right\rfloor $$ Only non-negative $k$ are valid (since $x, y \in \mathbb{N}$), so clamp $k_{\min} = \max(0, k_{\min})$. If $k_{\min} > k_{\max}$, the answer is 0; otherwise, it's $k_{\max} - k_{\min} + 1$.

Care must be taken with integer division in C++: standard / truncates toward zero. To correctly compute floor and ceiling divisions for possibly negative numerators, define helper functions:

long long floor_div(long long a, long long b) {
    if (b < 0) { a = -a; b = -b; }
    if (a >= 0) return a / b;
    return (a - b + 1) / b;
}

long long ceil_div(long long a, long long b) {
    if (b < 0) { a = -a; b = -b; }
    if (a >= 0) return (a + b - 1) / b;
    return a / b;
}

Final implementation steps:

1. Solve the Diophantine equation.
2. Adjust to the minimal non-negative solution.
3. Compute the first common value and the step size.
4. Count valid terms in $[l, r]$ using adjusted floor/ceil division.