upd on 04/27/25：发现该文没写完 
#中国剩余定理
给定下列关于 x 的一元同余方程组：
{x≡a1(modm1)x≡a2(modm2)⋮x≡ak(modmk) 其中对于 ∀1≤i,j≤k(i≠j)，满足 mi⊥mj。下面是求解该方程组的具体方法：
令 M=k∏i=1mi,Mi=Mmi，则 x=k∑i=1ai×Mi×M−1i(modM)。
其中，M−1i 是 Mi 在模 mi 意义下的逆元（所以 Mi×M−1i 的值并不是视觉上的 1）。
正确性证明：对于 ∀i∈{1,2,⋯,k}，有 Mi∣M；对于 ∀j∈{1,2,⋯,k} 且 j≠i，有 mi∣Mmj 即 mi∣Mj，即 Mj≡0(modmi)。
又 mi∣M 那么就有 x≡ai⋅Mi⋅Mi−1≡ai(modni)。
时间复杂度 O(nlogn)。注意求解逆元时要用到 exgcd。
int CRT(int k, int *a, int *m) {
int M = 1, x = 0;
static int M1[maxn], Mi[maxn];
for (int i = 1; i <= k; ++i)
M *= m[i];
for (int i = 1; i <= k; ++i) {
M1[i] = M / m[i];
Mi[i] = getinv(M1[i], m[i]);
(x += a[i] * M1[i] * Mi[i]) %= M;
}
return x;
}查看代码
#扩展中国剩余定理
设有如下同余方程组：
{x≡a1(modm1)x≡a2(modm2)
不保证 m1⊥m2。
设 x=m1×p1+a1=m2×p2+a2，其中 pi∈Z，则有 p1×m1−p2×m2=a2−a1。
p1 的值可以用 exgcd 求解，则原方程的解满足 x≡m1×p1+a1(modM)，其中 M=lcm(m1,m2)。
这样我们就得到了一个新的同余方程。对于 k>2 的情况，我们不断合并两个同余方程即可得到最终同余方程。
此时根据题目要求（一般求最小值即 mk×pk+ak）求解答案即可。
时间复杂度 O(nlogn)，其中 log 来自 exgcd。
int calc(int m1, int a1, int m2, int a2) {
int p1, p2;
if (a2 - a1 < 0)
swap(a1, a2), swap(m1, m2);
int g = exgcd(m1, p1, m2, p2);
if ((a2 - a1) % g)
return -1;
p1 *= (a2 - a1) / g, m2 /= g;
p1 = (p1 % m2 + m2) % m2;
return p1 * m1 + a1;
}
int exCRT(int k, int *a, int *m) {
for (int i = 2; i <= k; ++i) {
a[i] = calc(m[i - 1],
a[i - 1], m[i], a[i]);
if (a[i] == -1)
return -1;
m[i] = lcm(m[i - 1], m[i]);
}
return a[k] % m[k];
}查看代码
#D. Strange Way to Express Integers
http://222.180.160.110:1024/contest/3642/problem/4
板。但是要开 __int128。不知道为什么智力只用开 long long 就能跑过，我和揭哥就不行。
#define int __int128
namespace XSC062 {
using namespace fastIO;
const int maxn = 1e5 + 5;
int n;
int a[maxn], m[maxn];
int gcd(int x, int y) {
return y ? gcd(y, x % y) : x;
}
inline int lcm(int x, int y) {
return x / gcd(x, y) * y;
}
inline void swap(int &x, int &y) {
x ^= y ^= x ^= y;
return;
}
int exgcd(int a, int &x, int b, int &y) {
if (b == 0) {
x = 1, y = 0;
return a;
}
int u = exgcd(b, x, a % b, y);
int t = x;
x = y, y = t - (a / b) * y;
return u;
}
inline int calc(int m1, int a1,
int m2, int a2) {
int p1, p2;
if (a2 - a1 < 0)
swap(a1, a2), swap(m1, m2);
int g = exgcd(m1, p1, m2, p2);
if ((a2 - a1) % g)
return -1;
p1 *= (a2 - a1) / g, m2 /= g;
p1 = (p1 % m2 + m2) % m2;
return p1 * m1 + a1;
}
inline int exCRT(int k, int *a, int *m) {
for (int i = 2; i <= k; ++i) {
a[i] = calc(m[i - 1],
a[i - 1], m[i], a[i]);
if (a[i] == -1)
return -1;
m[i] = lcm(m[i - 1], m[i]);
}
return a[k] % m[k];
}
int main() {
while (read(n)) {
for (int i = 1; i <= n; ++i)
read(m[i]), read(a[i]);
print(exCRT(n, a, m), '\n');
}
return 0;
}
} // namespace XSC062
#undef int