扩展欧几里得(exgcd)与同余详解

exgcd入门以及同余基础

gcd，欧几里得的智慧结晶，信息竞赛的重要算法，数论的...（编不下去了

讲exgcd之前，我们先普及一下同余的性质：

4. 若，那么
5. 若，，且p1，p2互质，

有了这三个式子，就不用怕在计算时溢出了。

下面我会用与分别表示a与b的最大公约数与最小公倍数。

首先会来学扩欧的同学肯定都会欧几里得算法（即辗转相除法）了吧

而通过观察发现：，先除后乘防溢出。

所以与的代码如下：

 inline int gcd(int a,int b)

 {return (b==)?a:gcd(b,a%b);}

 inline int lcm(int a,int b)

 {return a/gcd(a,b)*b;

---

讲exgcd之前先引入一种方程——不定方程

所谓不定方程，是指未知数的个数多于方程个数，且未知数受到某些限制（如要求是有理数、整数或正整数等等）的方程或方程组。

————百度百科

就是形如的方程，其中a，b，c已知。

1.判断是否有解

如果，那么方程无解。

2.转化

方程可转化为，

其中，，

3.求一组特解

接着就用到了exgcd。

我们知道gcd有一个性质

如果，一直循环下去，b将等于0，那么x将等于c/a，y=0。

 inline void exgcd(int a,int b,int c)

 {

     if(!b)

     {x=c/a;y=;return;}

     exgcd(b,a%b,c);

     x=y;

     y=(c-a*x)/b;

     return;

 }

这就求出了一组特解。

exgcd的模板我也在这摆出来

 inline void exgcd(int a,int b)

 {

     if(!b)

     {x=;y=;return;}

     exgcd(b,a%b);

     k=x;x=y;

     y=k-a/b*y;

     return;

 }

这是求时用的，后面讲同余方程会讲。

4.构造通解

我们假设x1，y1是我们求出的一组特解，那么

    

---

同余类问题

1.单个同余方程

求的是关于x的解

转化一下，就成了，就可以直接套exgcd模板。

2.同余方程组

1.有解的充要条件

2.

下式减上式得

再用exgcd求出y1和y2，

3.关于通解

所有的x mod lcm(p1,p2)有唯一解，这样就可以通过特解，求通解了。

4.至于式子更多的同余方程组，就先联立两个，就可以得出新的方程

再联立下一个。

---

exgcd用处及题目讲解

1.求同余方程的解

例如这道题P1082

这是一道裸的扩欧模板题，变形之后就是求。

套模板即可。

 inline void exgcd(int a,int b)

 {

     if(b==)

     {x=;y=;return;}

     exgcd(b,a%b);

     k=x;x=y;

     y=k-a/b*y;

     return;

 }

 int main()

 {

     int n,m;

     read(n),read(m);

     exgcd(n,m);

     printf("%d",(x+m)%m);

 }

还有一道模板P1516

仔细观察，推一下后我们发现，这在就是在求的解。

进而可以推出

合并同类项后

把一些东西移到左边来后

把(x-y)，(n-m)各看成一个整体后，问题就成了解一个不定方程。

 inline int exgcd(long long a,long long b)

 {

     if(b==)

     {x=;y=;return a;}

     ans=exgcd(b,a%b);

     k=x;x=y;

     y=k-a/b*y;

     return ans;

 }

 int main()

 {

     long long x1,y1,m,n,l;

     read(x1),read(y1),read(m),read(n),read(l);

     if(n-m<)swap(x1,y1);

     exgcd(std::abs(n-m),l);

     if((x1-y1)%ans!=)

     printf("Impossible");

     else

     printf("%lld",((x*((x1-y1)/ans))%(l/ans)+(l/ans))%(l/ans));

 }

还有一道也是模板P4777，涉及同余方程组求解，上面已详细的讲了，近期我也会发一篇中国剩余定理的博客

 inline long long mul(long long a,long long b,long long mod)

 {

     long long res=;

     while(b>)

     {

         if(b&) res=(res+a)%mod;

         a=(a+a)%mod;

         b>>=;

     }

     return res;

 }

 long long exgcd(long long a,long long b,long long &x,long long &y)

 {

     if(!b)

     {x=;y=;return a;}

     long long gcd=exgcd(b,a%b,x,y);

     k1=x;x=y;

     y=k1-a/b*y;

     return gcd;

 }

 int main()

 {

     io::begin();

     io::read(n);

     for(register int i=;i<=n;i++)

     io::read(b1[i]),io::read(a1[i]);

     long long x,y,k;

     long long m=b1[],ans=a1[];

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

     {

         long long a=m,b=b1[i],c=(a1[i]-ans%b+b)%b;

         long long gcd=exgcd(a,b,x,y);

         long long p=b/gcd;

         x=mul(x,c/gcd,p);

         ans+=x*m;

         m*=p;

         ans=(ans%m+m)%m;

     }

     printf("%lld",(ans%m+m)%m);

 }

2.扩欧求逆元

这是一种很重要的算法，至于逆元怎么跟扩欧扯上关系，大家可以点这里乘法逆元及两道模板题详解

这里就不多赘述了，大家可以用扩欧a一下P3811，P2613。

---

我要讲的讲完了，如果觉得讲的还好，请关注我的blog，谢谢