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\n",(ans.first%b+b)%b); return 0; }