中国剩余定理的大致思路
#include<iostream>
using namespace std;
typedef long long LL;//数据范围比较大,所以用LL来存储
LL exgcd(LL a,LL b,LL &x,LL &y)
{
if(!b)
{
x=1,y=0;
return a;
}
LL d=exgcd(b,a%b,y,x);
y-=a/b*x;
return d;
}
int main()
{
int n;
LL a1,m1;
cin>>n>>a1>>m1;
LL x=0;
for(int i=1;i<n;i++)
{
LL a2,m2;
cin>>a2>>m2;
LL k1,k2;
LL d=exgcd(a1,a2,k1,k2);
if((m2-m1)%d)
{
x=-1;
break;
}
k1*=(m2-m1)/d;
//因为此时k1是k1*a1+k2*a2=d的解,所以要乘上(m2-m1)/d的倍数大小
LL t=abs(a2/d);
k1=(k1%t+t)%t;
//数据比较极端,所以只求k的最小正整数解
m1=k1*a1+m1;
//m1在被赋值之后的值为当前"x"的值,此时赋值是为了方便下一轮的继续使用
a1=abs(a1*a2/d);
//循环结束时a1的值为当前所有的a1,a2,……an中的最小公倍数
}
if(x!=-1)
x=(m1%a1+a1)%a1;
//当循环结束时,此时的值应该与最小公倍数取模,以求得最小正整数解
printf("%lld\n",x);
return 0;
}
写的真好 终于把他啃懂了
佬,借用一下笔记
看了这一篇和扩展欧几里得那一篇一下子就懂了,写的真好
感觉这段代码
m1=k1*a1+m1;
,直接解释为”m1就是上述推导过程的x0会好点” O.O%
大佬真好,啊啊啊啊啊啊啊啊啊啊,我懂了
▄█▀█●
###### ▄█▀█●
## ▄█▀█●
### ▄█▀█●
#### ▄█▀█●
##### ▄█▀█●
大佬 请问最后 m1为什么要%a1?
这里的m1=k1a1+m1就是x的值,就是方程的解。但是要输出最小正整数,所以取他们的模
谢谢大佬
这里的有些结论证明有点问题,不过不用管,把它当作性质记住即可
难得,很不错,加油
k1,k2的解集是怎么得到的是数学知识吗
大学数学里有,非齐次线性方程解的结构
懂了,感谢
证明是根据从无到有来的,你到好,直接从有到有。
呃呃呃,高中没学过分析法吗?
解析法一般不是要有”<=>”的符号吗?
不过真的很感谢作者
证明不是这样证明的 你要说得出结论 用结论代入证明 这算什么证明
?证明方法不是单一的啊为什么要将证明思路限定呢
感觉这篇作者的年龄不是很大,很多地方写的也很好,为什么不能鼓励鼓励呢
人家现在在冲刺高考hh
大学直接进acm校队了属于是
感谢
证明清晰,好文要顶