日常生活中我们会遇到一些不定方程，注意本文中所考虑的解都是整数解，如：
3 x + y = 5 3x+y=5 3x+y=5
我们可以知道这个方程有解，如： { x = 1 y = 2 , { x = 2 y = − 1 , { x = 3 y = − 4 . . . . . . { x = 1 + k y = 2 − 3 k \begin{cases}x=1\\y=2\end{cases},\begin{cases}x=2\\y=-1\end{cases},\begin{cases}x=3\\y=-4\end{cases}......\begin{cases}x=1+k\\y=2-3k\end{cases} {x=1y=2,{x=2y=−1,{x=3y=−4......{x=1+ky=2−3k
我们可以知道这个方程有无数的整数解。
我们的扩欧就是来解决形如：
a x + b y = gcd ( a , b ) ax+by=\gcd(a,b) ax+by=gcd(a,b)
这一类 x , y x,y x,y 整数解的求解问题的。
我们可以知道 gcd ( a , b ) = gcd ( b , a % b ) \gcd(a,b)=\gcd(b,a\%b) gcd(a,b)=gcd(b,a%b)。所以我们在设一个方程：
b x ′ + ( a % b ) y ′ = gcd ( b , a % b ) bx'+(a\%b)y'=\gcd(b,a\%b) bx′+(a%b)y′=gcd(b,a%b)
所以我们有：
a x + b y = b x ′ + ( a % b ) y ′ ax+by=bx'+(a\%b)y' ax+by=bx′+(a%b)y′
a x + b y = b x ′ + ( a − ⌊ a b ⌋ ⋅ b ) y ′ ax+by=bx'+(a-\lfloor\frac{a}{b}\rfloor\cdot b)y' ax+by=bx′+(a−⌊ba⌋⋅b)y′
a x + b y = a y ′ + b ⋅ ( x ′ − ⌊ a b ⌋ ⋅ y ′ ) ax+by=ay'+b\cdot(x'-\lfloor\frac{a}{b}\rfloor\cdot y') ax+by=ay′+b⋅(x′−⌊ba⌋⋅y′)
所以 x = y ′ , y = x ′ − ⌊ a b ⌋ ⋅ y ′ x=y',y=x'-\lfloor\frac{a}{b}\rfloor\cdot y' x=y′,y=x′−⌊ba⌋⋅y′
递归求解即可：
#pragma GCC optimize("Ofast","-funroll-loops","-fdelete-null-pointer-checks") #pragma GCC target("ssse3","sse3","sse2","sse","avx2","avx") #include<bits/stdc++.h> #define int long long using namespace std; int read() { char ch=getchar(); int f=1,x=0; while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=x*10+ch-'0'; ch=getchar(); } return f*x; } int a,b,x,y; void exgcd(int a,int b,int &x,int &y) { if(b==0) { x=1,y=0; return ; } exgcd(b,a%b,x,y); int xx=y; int yy=x-a/b*y; x=xx; y=yy; } signed main() { a=read();b=read(); exgcd(a,b,x,y); cout<<x<<" "<<y<<endl; return 0; }