求关于(x)的同余方程 (ax equiv 1 pmod {b})的最小正整数解。
将 (ax equiv 1 pmod {b}) 转换成(ax+by=1),而(ax+by=1)有解的充要条件是(1\% gcd(a,b) == 1),于是乎(gcd(a,b) == 1),题目明确一定有解,于是我们得到(gcd(a,b))的值为1。
通过exgcd可求得(ax+my=gcd(a,b)①)的解((x_0,y_0))(我们只关心(x)),则(ax+by=1②)的解可在(①)式两边同乘(frac{1}{gcd(a,b)}),得到(afrac{x}{gcd(a,b)}+bfrac{y}{gcd(a,b)} = 1),故((frac{x_0}{gcd(a,b)},frac{y_0}{gcd(a,b)}))为(②)式的一个解,而(gcd(a,b) == 1),所以((x_0,y_0))就是(②)式的一个解。
最小正整数解为((x_0\%frac{b}{gcd}+frac{b}{gcd})\%frac{b}{gcd}),由(gcd(a,b)==1)化简得((x_0\%b+b)%b)。
int a,b,x,y;
int exgcd(int a,int b,int &x,int &y)
{
if(b == 0)
{
x=1,y=0;
return a;
}
int g=exgcd(b,a%b,x,y);
int t=x;
x=y;
y=t-a/b*y;
return g;
}
int main()
{
cin>>a>>b;
int g=exgcd(a,b,x,y);
cout<<(x%b+b)%b<<endl;
//system("pause");
return 0;
}