扩展欧几里德算法
var
x,y,a,b,d:int64;
procedure gcd(a,b:int64);
var
t:int64;
begin
if (a mod b = 0) then
begin
x:=0;
y:=1;
end
else
begin
gcd(b,a mod b);
t:=x;
x:=y;
y:=t-(a div b)*y;
end;
end;
begin
readln(a,b);
d:=b;
gcd(a,b);
writeln((x mod d+d) mod d);
end.

刚看了一个小时扩展欧几里得。。。

sofa

Enjoy.

#include<cstdio>
#define LL long long
using namespace std;
LL A,B,X,Y;
LL ExGcd (LL a,LL b,LL &x,LL &y) {  
    
    if (!b) {x=1,y=0;return a;}
    int as=ExGcd(b,a%b,x,y);
    int t=x;x=y;y=t-(a/b)*y;
    return as;
    
}
int main () {
    
    scanf("%lld%lld",&A,&B);
    LL gcd=ExGcd(A,B,X,Y),lcm=A*B/gcd;
    while(X<0) {X+=lcm/A;Y-=lcm/B;}
    printf("%lld",X);
    return 0;
    
}