基础欧几里得算法看着就行
(57条消息) 欧几里得算法_daq0411的博客-CSDN博客_欧几里得算法
扩展欧几里得算法；x=y′,y=x′??ba???y′
#include<iostream>
using namespace std;
#define ll long long
ll n, a[16], m[16], Mi[16], mul = 1, X;
void exgcd(ll a, ll b, ll& x, ll& y) {if (b == 0) { x = 1; y = 0; return; }exgcd(b, a % b, x, y);int z = x; x = y, y = z - y * (a / b);
}
int main() {cin >> n;for (int t = 1; t <= n; ++t) {int M ;cin >> M; m[t] = M;mul *= M;//求a1-an的最小公倍数（两两互质）cin >> a[t];}for (int t = 1; t <= n; ++t) {Mi[t] = mul / m[t];//ki=M/aill x = 0, y = 0;exgcd(Mi[t], m[t], x, y);//找到一个常数pi使得pi*ki%ai=1X += a[t] * Mi[t] * (x < 0 ? x + m[t] : x);//答案等于x=（p1*k1*b1+p1*k2*b2.......）}printf("%lld", X % mul);return 0;
}中国剩余定理：
大概就是有一个未知数xx，以及nn个方程，即xx除a1a1余b1b1，除a2a2余b2b2 ... 除aiai余bibi,问xx是多少
注意前提条件aiai与ajaj互质（任意两个模数互质）
设MM为a1a1~anan的最小公倍数，则MM=a1a1 * a2a2 * ~ anan (两两互质)
设kiki=M/aiM/ai ， 并找到一个常数pipi 使得 pipi * kiki % aiai == 11
则答案xx= （p1 * k1 * b1p1?k1?b1 + p2 * k2 * b2p2?k2?b2 + ... + pn * kn * bnpn?kn?bn） % MM
因为x=xx=x % MM 因此xx为最小值