考虑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; } } }
全部评论
(2) 回帖