exgcd模板

(ax+by)
(=gcd(a,b))
(=gcd(b,a%b))
(=gcd(b,a-(a/b)*b))
(=bx'+(a-(a/b)*b)y')
(=ay'+(x'-(a/b)y')b)

(x=y')
(y=x'(a/b)y)

#include<cstdio>
#include<algorithm>
using namespace std;
pair<int,int> exgcd(int x,int y)
{
	if(x==1&&y==0)
	return make_pair(x,y);
	pair<int,int> ans=exgcd(y,x%y);
	return make_pair(ans.second,ans.first-(x/y)*ans.second);
} 
int main()
{
	int a,b;
	scanf("%d%d",&a,&b);
	pair<int,int> ans=exgcd(a,b);
	printf("%d
",(ans.first%b+b)%b);
	return 0;
}