还记得我初一的时候还没听说过exgcd，看到这道题，咦，这不就是不定方程吗，
于是推了一个小时，推出一个类似exgcd的东西，本质一样
以下 / / /表示取整的除(div)
a x − b y = c ax-by=c ax−by=c
x = b y + c a = ( b % a ) y + c a + b / a ⋅ y x=\frac{by+c}{a}=\frac{(b\%a)y+c}{a}+b/a\cdot y x=aby+c​=a(b%a)y+c​+b/a⋅y
因为 x x x为整数， b / a ⋅ y b/a\cdot y b/a⋅y为整数，所以 ( b % a ) y + c 能 被 a 整 除 (b\%a)y+c能被a整除 (b%a)y+c能被a整除
不妨设 a y ′ = ( b % a ) y + c ay'=(b\%a)y+c ay′=(b%a)y+c
则 ( b % a ) y − a y ′ = − c (b\%a)y-ay'=-c (b%a)y−ay′=−c
若 g c d ( a , b , c ) gcd(a,b,c) gcd(a,b,c)表示满足 a x − b y = c ax-by=c ax−by=c的其中一个 x x x
那么， y = g c d ( b % a , a , − c ) y=gcd(b\%a,a,-c) y=gcd(b%a,a,−c)
把 y y y代入原式，得到 g c d ( a , b , c ) = x = b y + c a = b ⋅ g c d ( b % a , a , − c ) + c a gcd(a,b,c)=x=\frac{by+c}{a}=\frac{b\cdot gcd(b\%a,a,-c)+c}{a} gcd(a,b,c)=x=aby+c​=ab⋅gcd(b%a,a,−c)+c​
#####曾经的代码（pascal，满满的回忆啊）：

var a,b:int64;
function gcd(a,b,c:int64):int64;
begin
if (a=0)or(b=0) then exit(1);
exit((gcd(b mod a,a,-c)*b+c) div a);
end;
begin
readln(a,b);
writeln((gcd(a,b,1)) mod b);
end.

#####现在的代码都是这样了

#include<bits/stdc++.h>
int a,b,x,y;
void ex_gcd(int a,int b,int &x,int &y){
    if (!b) x=1,y=0;
    else ex_gcd(b,a%b,y,x),y-=a/b*x;
}
int main(){
    scanf("%d%d",&a,&b);
    ex_gcd(a,b,x,y);
    printf("%d",(x+b)%b);
}

深入学习