青蛙兔子的约会
题目描述
每当晚上时，青蛙都会出来活动，白天休息。白天时，兔子就会出来活动，晚上休息。
青蛙一次可以跳
a
a
a 米，兔子一次可以跳
b
b
b 米，已知青蛙在坐标
0
0
0 的位置，兔子在坐标
n
n
n 的位置。
现在青蛙与兔子在明天白天有个约会，但是青蛙不想等太久兔子，他决定在今天夜晚时就开始行动。
但是青蛙又怕累，所以晚上时青蛙只会向兔子的方向跳
[
L
,
R
]
[L, R]
[L,R] 次。
问青蛙能否与兔子约会？
输入描述:
输入共 T + 1 T+1 T+1 行。
第一行一个整数表示 T ( 1 ≤ T ≤ 1 0 5 ) T(1 \leq T \leq 10^5) T(1≤T≤105)。
接下来 T T T 行，每行 5 5 5 个整数表示 a , b , n , L , R ( 1 ≤ a , b , n , L , R ≤ 1 0 9 , L ≤ R ) a,b,n,L,R(1 \leq a,b,n,L,R \leq 10^9, L≤R) a,b,n,L,R(1≤a,b,n,L,R≤109,L≤R)。
数据保证青蛙不会跳过 n n n 的位置，即 1 ≤ L a ≤ R a ≤ n 1 \leq La \leq Ra \leq n 1≤La≤Ra≤n。
输出描述:
输出共 T T T 行，每行一个"YES" 或 “NO”（不包括双引号），表示青蛙和兔子能否约会。
示例1
输入
3
3 4 10 1 2
2 4 5 1 1
3 5 11 1 1
输出
YES
NO
NO
说明
第一问，青蛙晚上向右跳
1
1
1 次，白天无法与兔子相遇。青蛙向右跳
2
2
2 次，也就是
2
a
=
6
2a=6
2a=6 的距离，白天兔子向左跳
1
1
1 次，可以相遇。所以在跳
[
1
,
2
]
[1,2]
[1,2] 次中，存在青蛙和兔子可以相遇。
第二问，青蛙晚上向右跳
1
1
1 次，然后无论白天兔子怎么跳，都无法和青蛙相遇。
题解
1 判断是否有整数解
该题目可以等价为：求解一个二元一次方程组的整数解。
即求解：
a
x
+
b
y
=
n
ax + by = n
ax+by=n 的正整数解，且
x
∈
[
L
,
R
]
x \in [L, R]
x∈[L,R]。
首先使用 裴蜀定理 来判断
a
x
+
b
y
=
n
ax + by = n
ax+by=n 是否有整数解。
判断过程为：
- 求 ( a , b ) (a, b) (a,b) 的最大公约数 d d d；
- 判断 d d d 是否能整除 n n n；
- 若能整除则有整数解，若不能则没有整数解。
2 求通解 = 特解+其次解
若
a
x
+
b
y
=
n
ax + by = n
ax+by=n 有整数解，且
d
=
g
c
d
(
a
,
b
)
d = gcd(a, b)
d=gcd(a,b)。
那么我们求该方程组的通解，并判断通解集合和
[
L
,
R
]
[L, R]
[L,R]是否有交集。有交集则有能约会，没有则不能约会。
我们使用扩展欧几里得算法求出
a
x
+
b
y
=
d
ax + by = d
ax+by=d 的一组特解：
(
x
0
,
y
0
)
(x_0, y_0)
(x0,y0)。
由此得出
a
x
+
b
y
=
n
ax + by = n
ax+by=n 的一组特解：
(
x
0
∗
n
d
,
y
0
∗
n
d
)
(x_0*\frac{n}{d}, y_0*\frac{n}{d})
(x0∗dn,y0∗dn)。
方程 a x + b y = 0 ax + by = 0 ax+by=0 的通解为： ( k ∗ b d , k ∗ a d ) , k ∈ Z (k*\frac{b}{d}, k*\frac{a}{d}), k \in \mathbb{Z} (k∗db,k∗da),k∈Z。
综上： a x + b y = n ax + by = n ax+by=n 的特解为： ( x 0 ∗ n d + k ∗ b d , y 0 ∗ n d + k ∗ a d ) , k ∈ Z (x_0*\frac{n}{d}+k*\frac{b}{d}, y_0*\frac{n}{d}+k*\frac{a}{d}), k \in \mathbb{Z} (x0∗dn+k∗db,y0∗dn+k∗da),k∈Z文章来源：https://www.toymoban.com/news/detail-443460.html
随后判断 { x ∣ x = x 0 ∗ n d + k ∗ b d , k ∈ Z } \{x|x = x_0*\frac{n}{d}+k*\frac{b}{d}, k \in \mathbb{Z}\} {x∣x=x0∗dn+k∗db,k∈Z} 和 [ L , R ] [L, R] [L,R] 是否有交集即可。详情看代码！文章来源地址https://www.toymoban.com/news/detail-443460.html
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll exgcd(ll a, ll b, ll &x, ll &y){
if (b == 0ll){
x = 1ll, y = 0ll;
return a;
}
ll d = exgcd(b, a % b, y, x);
y -= a / b * x;
return d;
}
int main(){
int t;cin>>t;
while(t--){
ll a, b, n, d, l, r, x0=0, y0=0;
scanf("%lld%lld%lld%lld%lld", &a, &b, &n, &l, &r);
d = exgcd(a, b, x0, y0); // d = gcd(a, b), (x0, y0)是 ax+by = d 的特解
if(n % d != 0){ // 没有整数解
cout<<"NO\n";
}
else{ // 有整数解
b = b/d;
ll x1 = x0*n/d; // ax+by=n 的特解
// 通解为 x = x1 + k*b
ll x = (x1 + b) % b; // 最小特解
x = x + l/b*b; // 接近 l 的解
while(x<l) x += b; // 找到第一个大于l的特解x
if(x <= r){ // 判断 第一个大于l的解x 是否小于等于 r
cout<<"YES\n";
}
else{
cout<<"NO\n";
}
}
}
return 0;
}
到了这里，关于青蛙兔子的约会的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
