# 数论模板

1.中国剩余定理 (互质版)

```#include <iostream>
using namespace std;
typedef long long LL;
LL ex_gcd(LL a, LL b, LL &x, LL &y);
LL China(LL re[], LL w[], LL len);

int main()
{
LL n, i;
LL a[50000], b[50000];
while (cin >> n)
{
for (i = 0; i < n; i++)
{
cin >> a[i] >> b[i];//除数，余数
}
cout << China(b, a, n) << endl;
}
return 0;
}

LL ex_gcd(LL a, LL b, LL &x, LL &y)//扩展gcd
{
LL d = 0;
if (b == 0)
{
x = 1; y = 0;
return a;
}
d = ex_gcd(b, a%b, y, x);
y -= a / b * x;
return d;
}

LL China(LL re[], LL w[], LL len)//中国剩余原理  re余数数组 w除数数组 len数组长度
{
LL i, d, x, y, m, n, ret;
ret = 0;
n = 1;
for (i = 0; i < len; i++)
n *= w[i];
for (i = 0; i < len; i++)
{
m = n / w[i];
d = ex_gcd(w[i], m, x, y);
ret = (ret + y * m*re[i]) % n;
}
return (n + ret % n) % n;
}```

2.中国剩余原理（万能版）

```#include<iostream>
#include<stdio.h>
using namespace std;
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 q = exgcd(b, a%b, y, x);
y -= a / b * x;
return q;
}
int main() {
long long a1, c1, a2, c2, x, y, t;
long long n;
while (cin >> n) {
long long flag = 1;
cin >> a1 >> c1;
for (long long i = 1; i < n; i++) {
cin >> a2 >> c2;
long long q = exgcd(a1, a2, x, y);
if ((c2 - c1) % q != 0) {
flag = 0;
}
t = a2 / q;
x = ((x*(c2 - c1) / q) % t + t) % t;
c1 = c1 + a1 * x;
a1 = a1 * (a2 / q);
}
if (flag == 0) {
cout << "-1" << endl;
continue;
}
cout << c1 << endl;
}
return 0;
}```

```#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long LL;

LL gcd(LL a, LL b)
{
if (b == 0)
return a;
return gcd(b, a%b);
}

LL ex_gcd(LL a, LL b, LL&x, LL& y)
{
if (b == 0)
{
x = 1, y = 0;
return a;
}
LL d = ex_gcd(b, a%b, x, y);
LL t = x;
x = y;
y = t - a / b * y;
return d;
}

LL inv(LL a, LL n)//求a在模n乘法下的逆元，没有则返回-1
{
LL x, y;
LL t = ex_gcd(a, n, x, y);
if (t != 1)
return -1;
return (x%n + n) % n;
}

//将两个方程合并为一个
bool merge(LL a1, LL n1, LL a2, LL n2, LL& a3, LL& n3)
{
LL d = gcd(n1, n2);
LL c = a2 - a1;
if (c%d)
return false;
c = (c%n2 + n2) % n2;
c /= d;
n1 /= d;
n2 /= d;
c *= inv(n1, n2);
c %= n2;
c *= n1 * d;
c += a1;
n3 = n1 * n2*d;
a3 = (c%n3 + n3) % n3;
return true;
}

//求模线性方程组x=ai(mod ni),ni可以不互质
LL ex_China(int len, LL* a, LL* n)
{
LL a1 = a[0], n1 = n[0];
LL a2, n2;
for (int i = 1; i < len; i++)
{
LL aa, nn;
a2 = a[i], n2 = n[i];
if (!merge(a1, n1, a2, n2, aa, nn))
return -1;
a1 = aa;
n1 = nn;
}
return (a1%n1 + n1) % n1;
}
LL a[1000], b[1000];
int main()
{
int i;
int k;
while (cin >> k)
{
for (i = 0; i < k; i++)
cin >> a[i] >> b[i];
cout << ex_China(k, b, a);
}
return 0;
}```