555

需要求关于 x 的同余方程 ax≡1(mod b) 的最小正整数解。

这道题可以转化为扩展欧几里得解线性同余方程的算法。

给定整数 a,b,m 对于这组数，求一个整数 x 使它满足 ax≡b(mod m)。

这道题就是特殊的线性同余方程，即变为了 ax≡1(mod b)。

我们可以先通过扩展欧几里得算法求出一组特解。

由于题目要求输出最小整数解x，因此再得到特解后，再通过处理即可得到最小整数解。

即

x = (x % b + b) % b;

--end