Exgcd
Rising_Date
·
·
算法·理论
求解不定方程 ax+by=gcd(a,b)
方法：Exgcd
推导过程
首先 gcd(a,b)=gcd(b,a\ mod\ b);
\ \ 因为 gcd(a,b)=ax1+by1
那么 gcd(b,a\ mod\ b)=bx_2+(a\ mod\ b)y_2
\ \ \ \ \ \ $又因为 $a\ mod\ b=a-(a/b)*b
所以 ax_1+by_1=bx_2+(a-(a/b)*b)y_2
\ \ \ \ 那么 ax_1+by_1=ay_2+b(x_2-(a/b)*y_2);
根据系数之间的一一对应关系 x_1=y_2,y_1=x_2-(a/b)y_2;
\ \ \ \ \ \ $当递归到 $gcd(a,0)=a$ 时，我们得到 $x=1,y=0$, 然后 $return ;
由此递归下去，即可得到该不定方程的一组解
对于通解:
假设 x0,y0 是当前解除的一组解
通解 x=x0+b/gcd(a,b)*k,
然后将 $x,y$ 代入原方程即可验证。
```c
//代码
#include<cstdio>
using namespace std;
int x,y;
inline int abs(int a){return a>0?a:-a;}
int exgcd(int a,int b){
if(!b){x=1,y=0;return a;}
int d=exgcd(b,a%b),t=x;
x=y,y=t-(a/b)*y;
return d;
}
int main(){
int a,b;
scanf("%d%d",&a,&b);
int d=exgcd(a,b);
if(c%d==0){
x*=c/d,t=abs(b/d);
x=(x%t+t)%t;
printf("%d",x);
}
return 0;
}
```
应用：**[](https://www.luogu.org/problemnew/show/P1516)青蛙的约会**