【文件属性】：
文件名称：中国剩余定理cpp代码
文件大小：949B
文件格式：CPP
更新时间：2021-01-19 13:49:40
中国剩余定理
#include
#include
using namespace std;
typedef int LL;
typedef pair PLL;
LL inv(LL t, LL p) {//求t关于p的逆元
if (t >= p)
t = t%p;
return t == 1 ? 1 : (p - p / t) * inv(p % t, p) % p;
}
LL gcd(LL a, LL b){
return b == 0 ? a : gcd(b, a%b);
}
PLL linear(LL A[], LL B[], LL M[], int n) {//求解A[i]x = B[i] (mod M[i]),总共n个线性方程组
LL x = 0, m = 1;
for (int i = 0; i < n; i++) {
LL a = A[i] * m, b = B[i] - A[i] * x, d =gcd(M[i], a);
if (b % d != 0) return PLL(0, -1);//答案不存在，返回-1
LL t = b / d * inv(a / d, M[i] / d) % (M[i] / d);
x = x + m*t;
m *= M[i] / d;
}
x = (x % m + m) % m;
return PLL(x, m);//返回的x就是答案，m是最后的lcm值
}
int main()
{
int n;
scanf_s("%d", &n);
LL a[2017], b[2017], m[2017];
for (int i = 0; i
