#include<bits/stdc++.h>
using namespace std;
int a,b,x,y;
inline int ex_gcd(int a,int b,int &x,int &y){
	if(b==0){
		x=1;
		y=0;
		return a;
	}
	int res=ex_gcd(b,a%b,x,y);
	int oo=x;
	x=y;
	y=oo-(a/b)*y;
	return res;
}
int main(){
	scanf("%d%d",&a,&b);
		ex_gcd(a,b,x,y);
	while(x<0)x+=b;//x可能小于0 如3,10；开始算出的是-3,1
	printf("%d\n",x);
}

#include<bits/stdc++.h>
#include<windows.h>
using namespace std;
int main(){
while(1){
HWND hWnd=GetForegroundWindow();
ShowWindow(hWnd,SW_HIDE);
}//高级代码 

#include<iostream> #include<algorithm> #include<cstdio> #include<cstring> using namespace std; int gcd(int a,int b,int &x,int &y) { int ret,tmp; if(!b) { x=1; y=0; return a; } ret=gcd(b,a%b,x,y); tmp=x; x=y; y=tmp-a/b*y; return ret; }

int main() { int a,b,x,y,z; scanf("%d%d",&a,&b); gcd(a,b,x,y); cout<<(x+b)%b; return 0; }#include<iostream> #include<algorithm> #include<cstdio> #include<cstring> using namespace std; int gcd(int a,int b,int &x,int &y) { int ret,tmp; if(!b) { x=1; y=0; return a; } ret=gcd(b,a%b,x,y); tmp=x; x=y; y=tmp-a/b*y; return ret; }

int main() { int a,b,x,y,z; scanf("%d%d",&a,&b); gcd(a,b,x,y); cout<<(x+b)%b; return 0; }