• 周一. 4月 22nd, 2024

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

【数论】线性模方程组

admin

11月 28, 2021

由于被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)无解 则方程组无解

代码:

 1 scanf("%d%d",&r1,&a1);
 2 for (i=2;i<=n;i++){
 3     scanf("%d%d",&r2,&a2);
 4     ll gc=extgcd(x,y,r1,r2);
 5     if ((a1-a2)%gc) bo=0;
 6     ll mo=r2/gc;
 7     x=(x*(a2-a1)/gc%mo+mo)%mo;
 8     a1+=r*x;
 9     r1*=r2/gc;
10 }

View Code

《【数论】线性模方程组》有一个想法
  1. Wow, incredible blog structure! How long
    have you ever been blogging for? you made running a blog look easy.
    The full glance of your website is magnificent, as neatly as the content material!
    You can see similar here sklep

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注