题意
每个人有三个属性,身体,情绪和智力,他们达到顶峰的周期分别是23, 28, 33。
现在给你一些信息,在某一年,某人在天的时候达到了身体巅峰,在
天达到了情绪巅峰,在
天达到了智力巅峰,然后问你,这个人在当年
天后达到的第一次巅峰是什么时候
思路
求解同余方程组
如何求解同余方程组可以查看我的上一篇题解拓展中国剩余定理
代码
/**
* author: andif
* created: 10.08.2023 22:37:17
**/
#include<bits/stdc++.h>
using namespace std;
#define de(x) cerr << #x << " = " << x << endl
#define dd(x) cerr << #x << " = " << x << " "
#define rep(i, a, b) for(int i = a; i < b; ++i)
#define per(i, a, b) for(int i = a; i > b; --i)
#define mt(a, b) memset(a, b, sizeof(a))
#define sz(a) (int)a.size()
#define fi first
#define se second
#define qc ios_base::sync_with_stdio(0);cin.tie(0)
#define eb emplace_back
#define all(a) a.begin(), a.end()
using ll = long long;
using db = double;
using pii = pair<int, int>;
using pdd = pair<db, db>;
using pll = pair<ll, ll>;
using vi = vector<int>;
const db eps = 1e-9;
int exgcd(int a, int b, int& x, int& y) {
if (!b) return x = 1, y = 0, a;
int g = exgcd(b, a % b, x, y);
tie(x, y) = make_tuple(y, x - a / b * y);
return g;
}
int main() {
qc;
auto gao = [&] (int r1, int p1, int r2, int p2) {
if (r1 < r2) {
swap(r1, r2);
swap(p1, p2);
}
int p = p1 * p2 / gcd(p1, p2);
int x = -1, y = -1;
int g = exgcd(p2, p1, y, x);
int d = (r1 - r2) / g;
// int y0 = y * d;
// dd(y), dd(x), dd(p2), dd(p1), dd(y * p2 + x * p1), de(g);
int x0 = y * d * p2 + r2;
// dd(d), dd(r2), de(x0);
if (x0 <= 0) {
x0 = x0 + (-x0 + p - 1) / p * p;
} else {
x0 = x0 - (x0 / p) * p;
}
return pair(p, x0);
};
int t; cin >> t;
while(t--) {
int p, e, i, d;
cin >> p >> e >> i >> d;
p %= 23; e %= 28; i %= 33;
auto [p1, r1] = gao(p, 23, e, 28);
auto [p2, r2] = gao(r1, p1, i, 33);
// de(r2);
if (r2 <= d) {
int dd = d - r2 + 1;
r2 = r2 + (dd + p2 - 1) / p2 * p2;
}
cout << r2 - d << '\n';
}
return 0;
}