扩展欧几里得——解ax+by = c、ax≡c(mod m)

文章目录

解ax+by = gcd(a, b)解ax+by = c方程最小非负整数解的处理同余式ax≡c(mod m)的求解

解ax+by = gcd(a, b)

扩展欧几里得算法可以用来解这样一个方程： $ax+by=gcd(a,b)$，其中a，b是起初给定的数值（根据数论中的相关定理可以证明肯定有整数解 ，我也信了）

欧几里得算法中(辗转相除法),它总是把求解gcd(a,b)转化为gcd(b,a%d)，当b=0时返回a，此时的a就是gcd，因为达到递归边界时，有a* 1+b* 0=gcd成立，此时也有x=1，y=0

int gcd(int a,int b) { if(b==0)return a; else return gcd(b,a%b); }

求：$ax+by=gcd(a,b)$的一组整数解（x,y），观察： ax+by = gcd(a, b)$⟹$两个未知数x，y

根据欧几里得算法里面a，b的变化规律，可以再写出一个辅助式子： bx₂+a%by₂ = gcd(b,a%b)$⟹$+两个未知数x₂，y₂

由欧几里得算法可知，若b $\ne$ 0：gcd(a,b)=gcd(b,a%b) 所以：ax+by = bx₂+a%by₂ 即：ax+by = bx₂+(a–(a/b)*b)y₂ 即：ax+by = ay₂+ b*(x₂–a/b*y₂) 所以：x = y₂，y = x₂–(a / b) y₂

如果一直这样下去，递归到边界：b=0时，返回x=1，y=0，回溯的过程我们就可以求出最初的x，y的值。

ax+by = gcd通解： a*b/gcd是a和b的最小公倍数

模板：

LL exgcd(LL a, LL b, LL &x, LL &y) { if(b==0) { x=1; y=0; return a; } LL gcd=exgcd(b,a%b,x,y); LL temp=x; x=y; y=temp-a/b*y; //LL gcd=exgcd(b,a%b,y,x); //y-=(a/b)*x; return gcd; }

解ax+by = c

ax+by = c存在解的充要条件是c%gcd==0，ax+by = c的通解和ax+by = gcd一样，唯一不同是初始解（x，y）不同：

方程最小非负整数解的处理

Question1：如果需要求该方程的最小非负整数解，该如何调整？ 1、ax+by = gcd(a, b) 容易发现 $ax+by=gcd(a,b)$等价于 $a(x-k\cdot b)+b(y+k\cdot a)=gcd(a,b)$

所以对于x的调整为x=(x%b+b)%b（x的每一个整数解以b为周期）

对于y的调整为y=(y%a+a)%a 2、ax+by = c 同上，因为 $ax+by=c$等价于 $a(x-k\cdot \frac{b}{gcd})+b(y+k\cdot \frac{a}{gcd})=c$

所以对于x的调整为$x=(x\%(\frac{b}{gcd})+\frac{b}{gcd})\%\frac{b}{gcd}$

对于y的调整为$y=(y\%\frac{a}{gcd}+\frac{a}{gcd})\%\frac{a}{gcd}$

同余式ax≡c(mod m)的求解

同余式：对于整数a、b、m来说，如果m整除a-b（即（a-b）%m==0），那么就说a与b模m同余，对应同余式为a≡b(mod m)，m为同余式的模。例如10与13模3同余，记为10=13（mod 3）。

此处要解决的就是同余式ax≡c(mod m)的求解。根据同余式的定义，有 （ax-c)%m=0成立，因此存在整数-y使得ax-c=-my，即得ax+my=c。

由扩展欧几里得中的结论，当c%gcd(a，m)==0，是方程才有解。

例题：https://www.luogu.org/problem/P1082 代码：

#include<bits/stdc++.h> using namespace std; typedef int LL; const int N=2e6; LL exgcd(LL a,LL b,LL &x,LL &y) { if(b==0) { x=1; y=0; return a; } LL gcd=exgcd(b,a%b,x,y); //a%b也可以写成a-a/b*b，最开始写成a-b*a/b可能爆精度了，wa了两次 LL temp=x; x=y; y=temp-a/b*y; return gcd; } int main() { LL a,b,x,y; while(scanf("%d%d",&a,&b)!=EOF) { exgcd(a,b,x,y); x=(x%b+b)%b; printf("%d\n",x); } }