牛客练习赛111 D青蛙兔子的约会

题目链接

示例1

输入

3 4 10 1 2

2 4 5 1 1

3 5 11 1 1

输出

YES

NO

NO

说明

第一问，青蛙晚上向右跳1次，白天无法与兔子相遇。青蛙向右跳2次，也就是2a=6的距离，白天兔子向左跳1次，可以相遇。所以在跳[1,2]次中，存在青蛙和兔子可以相遇。

第二问，青蛙晚上向右跳1次，然后无论白天兔子怎么跳，都无法和青蛙相遇。

解题思路：

青蛙白天休息，晚上行动，兔子相反。

题目给出了青蛙移动的限制，但兔子没有移动的限制

所有可以得出公式 ：存在x,y是整数 有 ax = n-by

公式解释，因为兔子可以随意跳，那么只需要满足青蛙跳到兔子跳y次能跳到的地方即可（设青蛙跳x次）

公式变形 ax+by = n

由裴蜀定理可知，n一定是gcd(a,b)的倍数，也就是说 gcd(a,b)|n

可以用扩展欧几里得算法得出gcd(a,b)和满足ax+by=gcd(a,b)的x和y

如果记为x’和y’

ax’+by’=gcd(a,b)

如果要满足ax+by=n 需要gcd(a,b)|n. 那么 ax+by=(n/gcd(a,b))(ax’+by’)=n

设gcd(a,b)=d

可得 x=x’*n/d y=y’*n/d

ax+by=n 变成 (n/d)x’a+b(n/d)*y’=d(n/d)

这里还是特解，需要求通解继续变形

ax+by=n 变成 (a/d)x+(b/d)y=n/d 那么gcd(a/d,b/d)=1;

根据扩展欧几里得的一个常用定理来得到通解

设x0=(n/d)x’ ,y0=(n/d)y’

那么x0+b/d * t 和 y0+a/d *t 是ax+by=n 的一个通解

则最小正整数解为:(x’ * (n/d) % (b /d) + (b / d) )% (b / d);

既然最小正整数解出来了，这题就好做了

的代码

#include 
using namespace std;
using i64 = long long;
i64 exgcd(i64 a, i64 b, i64 &x, i64 &y) {if (not b) {return x = 1, y = 0, a;}i64 d = exgcd(b, a % b, x, y);tie(x, y) = make_pair(y, x - a / b * y);return d;
}
int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int t;for (cin >> t; t; t -= 1) {i64 a, b, n, l, r, x, y;cin >> a >> b >> n >> l >> r;i64 d = exgcd(a, b, x, y);if (n % d) {cout << "NO\n";} else {b /= d;x = (x * (n / d) % b + b) % b;//最小正整数解i64 y = l / b * b + x;if (y < l) {y += b;}cout << (y <= r ? "YES\n" : "NO\n");}}
}

解析：

由上述解析可知，如果gcd(a,b)|n不成立，直接no,即n%d!=0