#include <map>
#include <cmath>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
using namespace std;
int a,b,x,y;
void gcd(int a,int b,int &x,int &y)
{
if(b==0)
{
x=1;
y=0;
}
else
{
gcd(b,a%b,x,y);
int t=x; x=y;
y=(t-(a/b)*x);
}
}
int main()
{
freopen("1781.in","r",stdin);
freopen("1781.out","w",stdout);
scanf("%d %d",&a,&b);
gcd(a,b,x,y);
while (x<=0) x+=b;
printf("%d",x);
return 0;
}

扩展欧几里德算法
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;
    
}