[ABC193E] Oversleeping

cloud2764scallop_eve · 2024-01-01 15:50:59 · 题解

前置芝士

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。

观察题目中要求，其实有两点：

1. 火车恰好在 B 站；
2. 高桥醒着。

那么就有了 t 需要满足的条件：

这是一个区间，不过所幸数据很小，可以直接不加优化枚举。

由于没有说明 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;
}

这里的两重循环也是可以像法一一样化为一重的，但我太懒了，可以自行尝试。