扩展欧几里得(ex_gcd)，中国剩余定理（CRT）讲解有代码

扩展欧几里得算法

　　求逆元就不说了。

　　ax+by=c

　　这个怎么求，很好推。

　　设d=gcd(a,b) 满足d|c方程有解，否则无解。

　　扩展欧几里得求出来的解是 x是 ax+by=gcd(a,b)的解。

　　对于c的话只需要x*c/gcd(a,b)%(b/d)即可，因为b/d的剩余系更小。

　　为什么这样呢？

　　设a'=a/d,b'=b/d 求出a'x+b'y=1的解，两边同时乘d，然后x也是ax+by=d的解，

　　然后因为b'的剩余系更小，所以%b’

中国剩余定理是合并线性方程组的

中国余数定理

　　转化为一个线性方程 ax+by=c

　　　a,b

　　　c,d

　　　num % a=b;

　　　num % c=d;

　　　求num最小正整数解;

　　　num=ax+b=cy+d

　　　ax-cy=d-b

　　　可以化为求解 ax≡(d-b)(mod c);

　　　ax+cy=d-b

　　　用ex_gcd求解出x;

　　　num=a*x+b;

　　　这样num mod a=b

　　　num mod c=d-b+b=d

　　　因为x为最小正整数解，所以num为最小解

　　　满足的集合为{x|x=num+k·[a,b],(k∈Z)}

　　　然后转化为%lcm(a,c)=num

　　　然后继续合并

附上代码，完美代码

 #include<cstdio>

 #include<algorithm>

 #include<iostream>

 #include<cmath>

 typedef long long ll;

 using namespace std;

 ll ex_gcd(ll a,ll b,ll &x,ll &y)

 {

     if (!b)

     {

         x=,y=;

         return a;

     }

     ll fzy=ex_gcd(b,a%b,x,y);

     ll t=x;

     x=y;y=t-a/b*y;

     return fzy;

 }

 int main()

 {

     int t;

     ll z1,z2,z3,z4;

     while (cin>>t)

     {

         bool flag=;

         scanf("%lld%lld",&z1,&z2);

         for (int i=;i<t;i++)

         {

             scanf("%lld%lld",&z3,&z4);

             if (flag) continue;

             ll a=z1,b=z3,c=z4-z2;

             ll x,y;

             ll d=ex_gcd(a,b,x,y);

             if (c%d!=)

             {

                 flag=;

                 continue;

             }

             ll t=b/d;

             x=(x*(c/d)%t+t)%t;//t的剩余系更小。

             z2=z1*x+z2;//得出num

             z1=z1*(z3/d);

             cout<<"z1="<<z1<<" z2="<<z2<<endl;

         }

         if (flag==) cout<<-<<endl;

         else cout<<z2<<endl;

     }

 }

巴特西

扩展欧几里得(ex_gcd)，中国剩余定理（CRT）讲解有代码

最新文章

热门文章

巴特西

扩展欧几里得(ex_gcd)，中国剩余定理（CRT）讲解 有代码

最新文章

热门文章

扩展欧几里得(ex_gcd)，中国剩余定理（CRT）讲解有代码