ABC315G - Ai + Bj + Ck = X (1 <= i, j, k <= N)

exgcd，即扩展欧几里得算法（Extended Euclidean Algorithm），是欧几里得算法的一个扩展版本。它用于求解两个整数a和b的最大公约数（Greatest Common Divisor，简称GCD），并且可以同时计算出满足贝祖等式 ax + by = gcd(a, b) 的整数解x和y。

题目大意

给定正整数 $N,A,B,C,X$ ，求满足以下要求的三元组 $(i,j,k)$ 的个数。

• $1 \le i,j,k \le N$
• $Ai+Bj+Ck=X$

思路

最暴力的做法是三重循环枚举 $i,j,k$，时间复杂度 $O(N^3)$。

优化一下，可以枚举 $i,j$，检查对应唯一的 $k$ 是否合法，时间复杂度 $O(N^2)$；

再换一个角度考虑，枚举每一个 $i$，并求出相对应的二元一次方程的合法解的数量，时间复杂度 $O(N \log N)$。这个过程可以通过使用 exgcd 求出方程的一个特解后，求出通解形式，再代入题目要求的不等式条件中求解。

实际上，由于 $B,C$ 是固定的，可以预处理好 $Bj+Ck=\gcd(B,C)$ 的特解，再在每个循环中 $O(1)$ 求出 $Bj+Ck=X-Ai$ 的特解（同时乘 $\frac{X-Ai}{gcd(B,C)}$），时间复杂度即为 $O(N)$。

代码

__int128 extend_gcd(__int128 a, __int128 b, __int128 &x, __int128 &y) {
    if (a == 0 && b == 0)
        return -1;
    if (b == 0) {
        x = 1, y = 0;
        return a;
    }
    __int128 d = extend_gcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}
__int128 ceil(__int128 x, __int128 y) {
    if (x % y == 0)
        return x / y;
    if (x < 0)
        return x / y;
    return x / y + 1;
}
__int128 floor(__int128 x, __int128 y) {
    if (x % y == 0)
        return x / y;
    if (x > 0)
        return x / y;
    return x / y - 1;
}
ll N, A, B, C, X, res;
int main() {
    ios;
    cin >> N >> A >> B >> C >> X;
    __int128 g = __gcd(B, C), j0, k0;
    B /= g, C /= g;
    extend_gcd(B, C, j0, k0);
    rep(i, 1, N) {
        __int128 x = X - A * i;
        if (x <= 0)
            break;
        if (x % g != 0)
            continue;
        else {
            x /= g;
            __int128 j = x * j0, k = x * k0;
            __int128 l[3], r[3];
            l[0] = ceil(1 - j, C);
            r[0] = floor((N - j), C);
            l[1] = ceil(k - N, B);
            r[1] = floor(k - 1, B);
            l[2] = max(l[0], l[1]), r[2] = min(r[0], r[1]);
            if (l[2] <= r[2])
                res += r[2] - l[2] + 1;
        }
    }
    cout << res;
    return 0;
}