链接:https://ac.nowcoder.com/acm/contest/635/H
来源:牛客网
艾兰岛和沃夫岛的时间算法很不一样,它们都拥有它们自己的魔法大时钟。
以我们的时间来看艾兰岛的大时钟起鸣在b, b+a, b+2a, b+3a,… ,(a,b均为正整数)
并且沃夫岛的大时钟起鸣在d, d+c, d+2c, d+3c,….(c,d均为正整数)因为计时的方法不同,
两边经常打仗,但可能有某些时间点两边的大时钟同时起鸣。我们称这样的时间点为和平点。
求第一个和平点。(如果没有这样的时间点,输出-1)
题意:求解方程: b + ax = d + cy
思路:将方程化成:ax - cy = d - b,然后使用扩展欧几里得算法,判断方程是否有解,即 (d - b) % gcd(a, -c) == 0
解出x的最小正解y。因为x >= 0 && y >= 0。
由于本人太菜,所有使用二分判断 y = (c - a * (x + mid * k)) / b (y >= 0 && x >= 0,是否成立来求解出x的值。
最后答案:,b+a*(x+k*tmp)
# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a, b, c, d, x, y, gd;
ll ex_gcd(ll a, ll b)
{
if(b == 0)
{
x = 1;
y = 0;
return a;
}
gd = ex_gcd(b, a%b);
ll t = x;
x = y;
y = t-(a/b)*y;
return gd;
}
int main()
{
ll A, B, C, D, t, tmp=0;
scanf("%lld%lld%lld%lld",&A,&B,&C,&D);
a = A;
b = -C;
c = D-B;
gd = ex_gcd(a, b);
if(c % gd != 0)
return 0*puts("-1");
x = x*c/gd;
y = y*c/gd;
ll k = b/gd;
x = (x%k+k)%k;
if(x < 0) x += abs(k);
k = abs(k);
ll l = 0, r = 1e9;
while (l <= r) {
ll mid = (l + r) / 2;
if (x + mid * k >= 1e9) {
r = mid - 1;
continue;
}
if ((c - a * (x + mid * k)) / b >= 0) {
r = mid - 1;
tmp = mid;
} else {
l = mid + 1;
}
}
printf("%lld\n",B+A*(x+k*tmp));
return 0;
}