Caddi Programming Contest 2021(AtCoder Beginner Contest 193) E.Oversleeping_atcoder oversleeping

Caddi Programming Contest 2021(AtCoder Beginner Contest 193) E.Oversleeping

题目链接

Problem Statement

A train goes back and forth between Town A and Town B. It departs Town A at time 0 and then repeats the following:

• goes to Town B, taking X seconds;
• stops at Town B for Y seconds;
• goes to Town A, taking X seconds;
• stops at Town A for Y seconds.

More formally, these intervals of time are half-open, that is, for each n=0,1,2,…:

• at time t such that (2X+2Y)n≤t<(2X+2Y)n+X, the train is going to Town B;
• at time t such that (2X+2Y)n+X≤t<(2X+2Y)n+X+Y, the train is stopping at Town B;
• at time t such that (2X+2Y)n+X+Y≤t<(2X+2Y)n+2X+Y, the train is going to Town A;
• at time t such that (2X+2Y)n+2X+Y≤t<(2X+2Y)(n+1), the train is stopping at Town A.

Takahashi is thinking of taking this train to depart Town
A at time 0 and getting off at Town B. After the departure, he will repeat the following:

• be asleep for P seconds;
• be awake for Q seconds.

Again, these intervals of time are half-open, that is, for each n=0,1,2,…:

• at time t such that (P+Q)n≤t<(P+Q)n+P, Takahashi is asleep;
• at time t such that (P+Q)n+P≤t<(P+Q)(n+1), Takahashi is awake.

He can get off the train at Town B if it is stopping at Town B and he is awake.Determine whether he can get off at Town B. If he can, find the earliest possible time to do so.Under the constraints of this problem, it can be proved that the earliest time is an integer.

You are given T cases. Solve each of them.

Sample Input 1

3
5 2 7 6
1 1 3 1
999999999 1 1000000000 1
1
2
3
4

Sample Output 1

Copy
20
infinity
1000000000999999999
1
2
3
4

拓展欧几里得~
题目就是求一个同余方程组：
{ t ≡ t 1 ( m o d   ( 2 X + 2 Y ) ) t ≡ t 2 ( m o d   ( P + Q ) )

$$\begin{cases} t\equiv t1(mod \ (2X+2Y))\\ t\equiv t2(mod \ (P+Q))\\ \end{cases}$$ {t≡t1(mod (2X+2Y))t≡t2(mod (P+Q))​
两式相减可以得：
$$(2X+2Y)x-(P+Q)y=t2-t1$$
因为题目中的 $Y,Q$ 都比较小，所以 $t1,t2$ 可以暴力遍历，上式可以通过拓展欧几里得定理求得一个特解 $x_0$，所以可以得到 $t$ 的一个特解 $t_0=(2X+2Y)\ast x_0+t1$，那么通解就是 $t=t_0+LCM(2X+2Y,P+Q)$，题目要求最小的正整数解，只需要将特解 $t_0$ 对 $LCM(2X+2Y,P+Q)$ 取模即可~
这题唯一的坑点就是会爆 $ll$，所以在最后算答案的时候要加快速乘，AC代码如下：

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

ll X, Y, ans, LCM, x, y, p, q, i, j;

void Gcd(ll A, ll B, ll &gcd) {
    if (B) {
        Gcd(B, A % B, gcd);
        ll t = X;
        X = Y;
        Y = t - (A / B) * Y;
    } else {
        gcd = A;
        X = 1, Y = 0;
    }
}

ll f(ll a, ll b, ll mod) {
    ll k = 0;
    while (b) {
        if (b & 1) k = (k + a) % mod;
        a = (a + a) % mod;
        b >>= 1;
    }
    return k;
}

void exgcd(ll A, ll B, ll C) {
    ll gcd;
    Gcd(A, B, gcd);
    if (C % gcd) return;
    else {
        X = X * (C / gcd);
        if (X < 0) X = (LCM - (-X) % LCM) % LCM;
        ans = min(ans, (f(2 * x + 2 * y, X, LCM) + i) % LCM);
    }
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        ans = INT64_MAX;
        cin >> x >> y >> p >> q;
        LCM = (2 * x + 2 * y) / __gcd(2 * x + 2 * y, p + q) * (p + q);
        for (i = x; i < x + y; i++) {
            for (j = p; j < p + q; j++) {
                exgcd(2 * x + 2 * y, -p - q, j - i);
            }
        }
        if (ans == INT64_MAX) cout << "infinity\n";
        else cout << ans << endl;
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57