前置芝士
exgcd 或 excrt。
解法一：exgcd
这道题的说明异常明显，对题目中给出的式子进行计算推导，最终是可以化成 exgcd 中类似于 \(ax + by = \gcd(a, b)\) 的形式的。但是因为我太菜了，不会具体的推导过程与证明，所以可以看看这篇题解。
代码
需要注意的是，由于数据无比大，所以要定义 const long long INF = 0x3f3f3f3f3f3f3f3f。
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll INF = 0x3f3f3f3f3f3f3f3f;
bool flag;
ll x, y, q, p, d, a, b, ans;
void Exgcd(ll a, ll b, ll &x, ll &y) {
if (!b) {
d = a, x = 1, y = 0;
return;
}
Exgcd(b, a % b, x, y);
ll t = x;
x = y, y = t - a / b * y;
}
int main() {
int T;
scanf("%d", &T);
while (T--) {
scanf("%lld%lld%lld%lld", &x, &y, &p, &q);
ans = INF, flag = 0;
Exgcd(2 * (x + y), p + q, a, b);
for (ll i = p - (x + y - 1); i <= p + q - 1 - x; i++) {
if (i % d != 0) continue;
flag = 1;
ll k = i / d, t = a * k;
t = (t % ((p + q) / d) + ((p + q) / d)) % ((p + q) / d);
if (i >= p - x) ans = min(ans, t * 2 * (x + y) + x);
else ans = min(ans, t * 2 * (x + y) + x + (p - x - i));
}
if (!flag) puts("infinity");
else printf("%lld\n", ans);
}
return 0;
}
解法二：excrt
为了方便表示，我们设高桥下车的时间为 \(t\)。
观察题目中要求，其实有两点：
- 火车恰好在 B 站；
- 高桥醒着。
那么就有了 \(t\) 需要满足的条件：
\(\begin{cases}
t \equiv x + i \pmod{(2x + 2y)}\\
t \equiv P + j \pmod{(P + Q)}
\end{cases}\)
这是一个区间，不过所幸数据很小，可以直接不加优化枚举。
由于没有说明 \(2x+2y\) 和 \(P + Q\) 互质，所以是 excrt。
代码
同样，请注意 INF 的赋值与多测清零和赋值。
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll mod = 1e9 + 7, INF = 0x3f3f3f3f3f3f3f3f;
ll x, y, p, q, ans;
ll a[15],b[15];
ll qmul(ll a, ll b, ll mod) {
ll res = 0;
while (b) {
if (b & 1) res = (res + a) % mod;
a = (a + a) % mod;
b >>= 1;
}
return res;
}
ll exgcd(ll a, ll b, ll &x, ll &y) {
if (!b) {
x = 1, y = 0;
return a;
}
ll d = exgcd(b, a % b, x, y);
ll t = x;
x = y, y = t - (a / b) * y;
return d;
}
ll excrt(ll n, ll ai[], ll bi[]) {
ll x, y;
ll m = bi[1], ans = ai[1];
for (int i = 2; i <= n; i++) {
ll a = m, b = bi[i], c = (ai[i] - ans % b + b) % b;
ll gcd = exgcd(a, b, x, y), bg = b / gcd;
if (c % gcd != 0) return -1;
x = qmul(x, c / gcd, bg);
ans += x * m;
m *= bg;
ans = (ans % m + m) % m;
}
return (ans % m + m) % m;
}
int main() {
int T;
scanf("%d", &T);
while (T--) {
bool flag = 0;
ans = INF;
scanf("%lld%lld%lld%lld", &x, &y, &p, &q);
for (int i = x ; i < x + y ; i++) {
for (int j = p ; j < p + q ; j++) {
a[1] = i, b[1] = 2 * (x + y);
a[2] = j, b[2] = p + q;
ll res = excrt(2, a, b);
if (res == -1) continue;
flag = 1;
ans = min(ans, res);
}
}
if (!flag) puts("infinity");
else printf("%lld\n", ans);
}
return 0;
}
这里的两重循环也是可以像法一一样化为一重的，
但我太懒了，可以自行尝试。