题解 | #Biorhythms#

【Biorhythms】 当三重峰值出现时，一定满足$x=p+23t_1=e+28t_2=i+33t_{3}x=p+23t\_1=e+28t\_2=i+33t\_3$​​，可以列出同余方程为

直接套excrt，求出通解。

注意题目要求的是从日期d​到下一个三重峰的天数，要求出特解。

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 1e5 + 10;

int exgcd(int a, int b, int &x, int &y) {
    if (!b) {
        x = 1, y = 0;
        return a;
    }
    int nx, ny;
    int d = exgcd(b, a % b, nx, ny);
    x = ny;
    y = nx - a / b * ny;
    return d;
}

int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }

int lcm(int a, int b) { return a / gcd(a, b) * b; }

pair<int, int> excrt(int k, int *a, int *r) {
    int M = r[1], ans = a[1];
    for (int i = 2; i <= k; i++) {
        int x0, y0;
        int c = a[i] - ans;
        int g = exgcd(M, r[i], x0, y0);
        if (c % g != 0) return {-1, -1};
        x0 = (__int128)x0 * (c / g) % (r[i] / g);
        ans = x0 * M + ans;
        M = lcm(M, r[i]);
        ans = (ans % M + M) % M;
    }
    return {ans, M};
}

int T, p, e, i, d;
int a[10], b[10];
signed main() {
    cin >> T;
    while (T--) {
        cin >> p >> e >> i >> d;
        a[1] = p, b[1] = 23;
        a[2] = e, b[2] = 28;
        a[3] = i, b[3] = 33;
        pair<int, int> w = excrt(3, a, b);
        w.first -= d;
        w.first = (w.first % w.second + w.second) % w.second;
        if (w.first == 0) w.first = w.second;
        cout << w.first << "\n";
    }

    return 0;
}