const long long MAXN = 100000000;
bool vis[MAXN + 5];
long long ptot, pri[5761455 + 5]; // pri 数组大小应为 MAXPTOT
// 筛 0~n 的质数 pri[1]~pri[ptot]
void genPrime(long long n)
{
ptot = 0;
for (long long i = 2; i <= n; ++i)
{
if (!vis[i])
pri[++ptot] = i;
for (long long j = 1; j <= ptot; ++j)
{
if (i * pri[j] > n)
break;
vis[i * pri[j]] = 1;
if (i % pri[j] == 0)
break;
}
}
}
const int MAXN = 512345;
bool vis[MAXN];
int ptot, phi[MAXN], pri[MAXN];
// 筛 0~MAXN-1 的欧拉函数与质数 pri[0]~pri[ptot-1]
void init()
{
phi[1] = 1;
for (int i = 2; i < MAXN; ++i)
{
if (!vis[i])
phi[i] = i - 1, pri[ptot++] = i;
for (int j = 0; j < ptot; ++j)
{
if (1ll * i * pri[j] >= MAXN)
break;
vis[i * pri[j]] = 1;
if (i % pri[j])
phi[i * pri[j]] = phi[i] * (pri[j] - 1);
else
{
phi[i * pri[j]] = phi[i] * pri[j];
break;
}
}
}
}
费马小定理： 为质数时，
所以： 为质数时，
// a^b (mod p)
long long quick_pow(long long a, long long b, long long p)
{
long long res = 1;
while (b)
{
if (b & 1)
res = (res * a) % p;
b = b >> 1;
a = (a * a) % p;
}
return res;
}
//求 x 在模 p 意义下的逆元（要求 p 是一个质数）
long long inv(long long x, long long p)
{
return quick_pow(x, p - 2, p);
}
扩展欧几里得定理：用于求方程 的解。
等式两边对 取模后为：， 在模 意义下存在逆元时保证 ，所以 。
void extend_gcd(int a, int b, int &x, int &y)
{
if (b == 0)
{
x = 1;
y = 0;
return;
}
extend_gcd(b, a % b, x, y);
int x2 = y;
int y2 = x - a / b * y;
x = x2;
y = y2;
}
//求 x 在模 p 意义下的逆元
int inv(int x, int p)
{
int res, y;
extend_gcd(x, p, res, y);
res = (res + p) % p;
return res;
}
求解 使得 。
显然:
两边同时对 取余得到：
两边同时乘以 得到：。
得到：
inv[1] = 1;
for (int i = 2; i <= n; i++)
inv[i] = (- p / i + p) * inv[p % i] % p;
luogu: P1495 【模板】中国剩余定理（CRT）/ 曹冲养猪
#include <bits/stdc++.h>
using namespace std;
long long n;
long long a[15], b[15];
long long M, m[15], t[15];
long long exGcd(long long a, long long b, long long &x, long long &y)
{
if (b == 0)
{
x = 1, y = 0;
return a;
}
long long xx, yy;
long long gcd = exGcd(b, a % b, xx, yy);
x = yy;
y = xx - (a / b) * yy;
return gcd;
}
long long inv(long long a, long long b)
{
long long x, y;
long long gcd = exGcd(a, b, x, y);
return (x % b + b) % b;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
// x % a[i] == b[i]
for (long long i = 1; i <= n; i++)
cin >> a[i] >> b[i];
// 计算 M = a[1] * a[2] * ... * a[n]
M = 1;
for (long long i = 1; i <= n; i++)
M *= a[i];
// 计算 m[i] = M / a[i]
// m[i] 是 a[j] 的倍数，且与 a[i] 互质
// t[i] 为 M 在模 a[i] 意义下的逆元
for (long long i = 1; i <= n; i++)
{
m[i] = M / a[i];
t[i] = inv(m[i], a[i]);
}
// m[i]*t[i] % a[i] == 1
// m[i]*t[i] % a[j] == 0
// b[i]*m[i]*t[i] % a[i] == b[i]
// b[i]*m[i]*t[i] % a[j] == 0
long long ans = 0;
for (int i = 1; i <= n; i++)
ans = (ans + b[i] * m[i] % M * t[i]) % M;
cout << ans << "\n";
return 0;
}
luogu: P4777 【模板】扩展中国剩余定理（EXCRT）
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n;
int a[112345], b[112345];
int exGcd(int a, int b, int &x, int &y)
{
if (b == 0)
{
x = 1, y = 0;
return a;
}
int xx, yy;
int gcd = exGcd(b, a % b, xx, yy);
x = yy;
y = xx - (a / b) * yy;
return gcd;
}
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;
}
//龟速乘
int mul(int a, int b, int p)
{
int res = 0;
while (b)
{
if (b & 1)
res = (res + a) % p;
b = b >> 1;
a = (a + a) % p;
}
return res;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i] >> b[i];
int a0 = a[1];
int b0 = b[1];
for (int i = 2; i <= n; i++)
{
// x0 % a0 = b0, x % a[i] = b[i]
// X * a0 + b0 === b[i] (mod a[i])
// X * a0 === (b[i] - b0) % a[i] (mod a[i])
// X * a0 + Y * a[i] = (b[i] - b0) % a[i]
int A = a0;
int B = a[i];
int C = ((b[i] - b0) % a[i] + a[i]) % a[i];
int X, Y;
int d = exGcd(A, B, X, Y);
X = mul(X, (C / d), (B / d));
b0 += X * a0;
a0 = lcm(a0, a[i]);
b0 = ((b0 % a0) + a0) % a0;
}
cout << b0 << endl;
return 0;
}