81 lines
2.4 KiB
C++
81 lines
2.4 KiB
C++
#include <bits/stdc++.h>
|
||
|
||
using namespace std;
|
||
|
||
typedef long long LL;
|
||
int a[20], m[20], n;
|
||
|
||
//【模板】中国剩余定理
|
||
// https://www.bilibili.com/video/av25823277
|
||
// https://xiaoxiaoh.blog.csdn.net/article/details/103024423
|
||
|
||
//扩展欧几里得
|
||
LL exgcd(LL a, LL b, LL &x, LL &y) {
|
||
if (b == 0) {
|
||
x = 1, y = 0;
|
||
return a;
|
||
}
|
||
LL d = exgcd(b, a % b, y, x);
|
||
y -= a / b * x;
|
||
return d;
|
||
}
|
||
|
||
//中国剩余定理
|
||
LL CRT() {
|
||
LL ans = 0;
|
||
LL M = 1;
|
||
LL t1, t2;
|
||
for (int i = 1; i <= n; i++) M *= m[i]; //M:所有除数的公倍数,因为是两两互质的，所以，也是最小公倍数
|
||
|
||
for (int i = 1; i <= n; i++) {
|
||
LL Mi = M / m[i]; //Mi:把自己除掉后，其它几个除数的乘积
|
||
//求逆元的过程
|
||
//求exgcd(e, m)—>利用欧几里得算法不断递归直到x=1,y=0—>反向递归求出第一层的x和y，x即为e模m的逆元。
|
||
exgcd(Mi, m[i], t1, t2); //t1就是逆元
|
||
ans = (ans + a[i] * Mi % M * t1) % M; //这个就是套用推导出来的公式了
|
||
}
|
||
return (ans + M) % M; //保证结果为正整数
|
||
}
|
||
|
||
// 快乘模板
|
||
// https://www.cnblogs.com/Fy1999/p/8908522.html
|
||
LL qmul(LL a, LL b, LL m) {
|
||
LL ans = 0;
|
||
while (b) {
|
||
if (b & 1) ans = (ans + a) % m;
|
||
a = (a << 1) % m;
|
||
b >>= 1;
|
||
}
|
||
return ans;
|
||
}
|
||
|
||
//中国剩余定理(快乘版本)
|
||
LL CRT_QickMul() {
|
||
LL ans = 0;
|
||
LL M = 1;
|
||
LL x, y;
|
||
for (int i = 1; i <= n; i++) M *= m[i];
|
||
for (int i = 1; i <= n; i++) {
|
||
LL Mi = M / m[i];
|
||
exgcd(Mi, m[i], x, y);
|
||
x = (x % m[i] + m[i]) % m[i]; //变成最小正整数解,这是为了快乘的特点,转换为最小正整数
|
||
//写一句 //d=(d%MOD+MOD)%MOD; 转化成正数就可以了,网上很多人也是这样做的,尤其在加密解密时。
|
||
ans = (ans + qmul(a[i] * Mi % M, x , M)) % M;
|
||
}
|
||
return (ans + M) % M; //防止为负数
|
||
}
|
||
int main() {
|
||
//输入+输出重定向
|
||
freopen("../AcWing/N11/China.txt", "r", stdin);
|
||
|
||
scanf("%d", &n);
|
||
for (int i = 1; i <= n; i++) {
|
||
scanf("%d%d", m + i, a + i); //m是除数,2是余数 ,注意这里数组的数据读入方法,还有下标的开始位置
|
||
}
|
||
printf("%lld\n", CRT());
|
||
|
||
printf("%lld\n", CRT_QickMul());
|
||
//关闭文件
|
||
fclose(stdin);
|
||
return 0;
|
||
} |