【数论】线性模方程组

由于被AK大神误导 - - 导致之前写了一个完全错误的总结 特此修改之

求方程组 x=a[i](mod r[i]) 的解x

即为求解方程 x=a[i]+r[i]*y

联想普通方程组的解法 一直将两个方程合并成一个 最后只剩一个方程 求解即可

设待合并的两个方程为 x=a1+r1*y、x=a2+r2*z

合并之

a1+r1*y=a2+r2*z

->r1*y+r2*z=a2-a1

拓展欧几里得求出(y,z)

则x最小为a1+r1*y

这时两方程合并为 x=a1+r1*y(mod lcm(r1,r2))

就这样两两合并 如果某次(y,z)无解 则方程组无解

代码：

scanf("%d%d",&r1,&a1);
for (i=2;i<=n;i++){
    scanf("%d%d",&r2,&a2);
    ll gc=extgcd(x,y,r1,r2);
    if ((a1-a2)%gc) bo=0;
    ll mo=r2/gc;
    x=(x*(a2-a1)/gc%mo+mo)%mo;
    a1+=r*x;
    r1*=r2/gc;
}