两份几乎一样的代码,只有龟速乘传参的位置有变化 前一份过了,而后一份 TLE。
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
void read() {}
template<typename T, typename ...U> void read(T &x, U& ...arg) {
x = 0; int f = 1; char ch = getchar();
while (ch > '9' || ch < '0') { if (ch == '-') f = -1; ch = getchar(); }
while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
x *= f; read(arg...);
}
void write() {}
template<typename T> void write(T x) {
if (x < 0) { putchar('-'), x = -x; }
if (x > 9) write(x / 10);
putchar(x % 10 + '0');
}
template<typename T, typename U> void write(T x, U y) {
write(x); putchar(y);
}
template<typename T> void chkmin(T &a, T b) { a = min(a, b); }
template<typename T> void chkmax(T &a, T b) { a = max(a, b); }
#define rep(i, a, b) for (int i = (a); i <= (b); i++)
#define per(i, a, b) for (int i = (a); i >= (b); i--)
int n;
i64 a1, m1, a2, m2, p;
i64 mul(i64 a, i64 b, i64 mod) {
i64 res = 0;
for (; b; b >>= 1) {
if (b & 1) res = (res + a) % mod;
a = (a + a) % mod;
}
return res;
}
i64 exgcd(i64 a, i64 b, i64 &x, i64 &y) {
if (!b) return x = 1, y = 0, a;
i64 d = exgcd(b, a % b, y, x); y -= a / b * x;
return d;
}
void exCRT() {
read(m1, a1);
rep(i, 1, n - 1) {
read(m2, a2);
i64 d = exgcd(m1, m2, p, *new i64);
i64 dif = ((a2 - a1) % m2 + m2) % m2;
if (dif % d) { return puts("-1"), void(); }
p = mul(p, dif / d, m2); (a1 += mul(p, m1, m1 / d * m2)) %= (m1 / d * m2);
m1 = m1 / d * m2; a1 = (a1 % m1 + m1) % m1;
}
write(a1);
}
int main() {
#ifdef LOCAL
freopen("code.in", "r", stdin);
freopen("code.out", "w", stdout);
auto start_time = chrono::high_resolution_clock::now();
#endif
read(n); exCRT();
#ifdef LOCAL
auto end_time = chrono::high_resolution_clock::now();
auto duration = chrono::duration_cast<chrono::milliseconds>(end_time - start_time);
cerr << "Time cost " << duration.count() << " ms" << endl;
#endif
return 0;
}
// START AT 2025 / 07 / 22 08 : 58 : 28
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
void read() {}
template<typename T, typename ...U> void read(T &x, U& ...arg) {
x = 0; int f = 1; char ch = getchar();
while (ch > '9' || ch < '0') { if (ch == '-') f = -1; ch = getchar(); }
while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
x *= f; read(arg...);
}
void write() {}
template<typename T> void write(T x) {
if (x < 0) { putchar('-'), x = -x; }
if (x > 9) write(x / 10);
putchar(x % 10 + '0');
}
template<typename T, typename U> void write(T x, U y) {
write(x); putchar(y);
}
template<typename T> void chkmin(T &a, T b) { a = min(a, b); }
template<typename T> void chkmax(T &a, T b) { a = max(a, b); }
#define rep(i, a, b) for (int i = (a); i <= (b); i++)
#define per(i, a, b) for (int i = (a); i >= (b); i--)
int n;
i64 a1, m1, a2, m2, p;
i64 mul(i64 a, i64 b, i64 mod) {
i64 res = 0;
for (; b; b >>= 1) {
if (b & 1) res = (res + a) % mod;
a = (a + a) % mod;
}
return res;
}
i64 exgcd(i64 a, i64 b, i64 &x, i64 &y) {
if (!b) return x = 1, y = 0, a;
i64 d = exgcd(b, a % b, y, x); y -= a / b * x;
return d;
}
void exCRT() {
read(m1, a1);
rep(i, 1, n - 1) {
read(m2, a2);
i64 d = exgcd(m1, m2, p, *new i64);
i64 dif = ((a2 - a1) % m2 + m2) % m2;
if (dif % d) { return puts("-1"), void(); }
p = mul(p, dif / d, m2); a1 += mul(m1, p, m1 / d * m2);
m1 = m1 / d * m2; a1 = (a1 % m1 + m1) % m1;
}
write(a1);
}
int main() {
#ifdef LOCAL
freopen("code.in", "r", stdin);
freopen("code.out", "w", stdout);
auto start_time = chrono::high_resolution_clock::now();
#endif
read(n); exCRT();
#ifdef LOCAL
auto end_time = chrono::high_resolution_clock::now();
auto duration = chrono::duration_cast<chrono::milliseconds>(end_time - start_time);
cerr << "Time cost " << duration.count() << " ms" << endl;
#endif
return 0;
}
// START AT 2025 / 07 / 22 08 : 58 : 28
这是为什么,我不能理解啊