中国剩余定理必须有两两互质的条件；而扩展中国剩余定理没有限制（可能互质，也能不互质）。所以只记忆一个扩展中国剩余定理的板子就行.文章来源：https://www.toymoban.com/news/detail-638149.html
文章来源地址https://www.toymoban.com/news/detail-638149.html
代码
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
int n;
LL exgcd(LL a, LL b, LL &x, LL &y){
if(b==0){
x = 1, y = 0;
return a;
}
LL d, x1, y1;
d = exgcd(b, a%b, x1, y1);
x = y1, y = x1 - a/b*y1;
return d;
}
LL excrt(LL m[], LL r[]){
LL m1, m2, r1, r2, p, q;
m1 = m[0], r1 = r[0];
for(int i = 1; i < n; ++i){
m2 = m[i], r2 = r[i];
LL d = exgcd(m1, m2, p, q);
if( (r2-r1)%d !=0 ) return -1; // 不能整除，说明无解
p = p*(r2-r1)/d;
p = (p%(m2/d) + (m2/d))%(m2/d);
r1 = m1*p+r1;
m1 = m1*m2/d;
}
return (r1%m1+m1)%m1;
}
int main(){
cin >> n;
LL m[30], r[30];
for(int i = 0;i < n; ++i){
cin >> m[i] >> r[i];
}
cout << excrt(m, r) << endl;
return 0;
}
题目
| 题目 | 难度 |
|---|---|
| AcWing.表达整数的奇怪方式 | 模板题 |
到了这里，关于中国剩余定理以及扩展中国剩余定理的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
