【算法】扩展欧几里德算法
【题解】学完扩欧就可以随便水了。。。
转化为不定方程ax-by=1。
因为1且题目保证有解，所以方程有唯一解。
紫书曰：同余方程的一个解其实指的是一个同余等价类。
所以满足x≡x‘(mod b)的其他x‘也是方程的解。
题目求最小正整数解，因此ans=x%b。
#include<cstdio> #define ll long long void gcd(ll a,ll b,ll& g,ll& x,ll& y) { if(!b){g=a;x=1,y=0;} else{gcd(b,a%b,g,y,x);y-=x*(a/b);} } int main() { ll A,B; scanf("%lld %lld",&A,&B); ll G,X,Y; gcd(A,B,G,X,Y); printf("%lld",(X+B)%B); return 0; }
原文：http://www.cnblogs.com/onioncyc/p/6146142.html
