d exgcd

考虑a只能跳l-r次，先让a跳l次，再求最小正整数解x使得ax+by=n-a*l，先用exgcd求出ax+by=gcd(a,b)的x和y任意解，设c=n-a*l，当c%gcd(a,b)为0时有解，此时设d=c/gcd(a,b),ax+by=c的解为x*d,y*d,设t=b/d,x的最小正数解为ans=(x%t+t%t),判断ans是否<=r-l即可

#include <iostream>
using namespace std;
#define int long long
int exgcd(int a, int b, int &x, int &y)
{
    if (!b)
    {
        x = 1, y = 0;
        return a;
    }
    else
    {
        int d = exgcd(b, (a % b + b) % b, y, x);
        y -= a / b * x;
        return d;
    }
}
signed main()
{
    int T = 1;
    cin >> T;
    while (T--)
    {
        int n, a, b, l, r, x, y;
        cin >> a >> b >> n >> l >> r;
        int d = exgcd(a, b, x, y);
        int c = n - l * a;
        // cout << x << " " << y << endl;
        if (c % d != 0)
        {
            cout << "NO" << endl;
        }

        else
        {
            x = x * (c / d), y = y * (c / d);
            int t = b / d;
            // cout << x << " " << c << " " << d << endl;
            int ans = (x % t + t) % t; // 最小正数解
            if (ans <= r - l)
            {

                int m1 = ans * a;
                int m2 = c - m1;
                // cout << ans << " " << m1 << " " << m2 << " " << c << endl;
                if (m2 % b == 0)
                {
                    cout << "YES" << endl;
                }
                else
                    cout << "NO" << endl;
            }
            else
                cout << "NO" << endl;
        }
    }
}