P1082 [NOIP 2012 Senior] Congruence Equation

Find the smallest positive integer solution of $ x$ to the congruence equation $ a x \equiv 1 \pmod {b}$.

One line containing two integers $a,b$, separated by a single space.

A single integer $x_0$, which is the smallest positive solution. The input is guaranteed to have a solution.

### Constraints - For $40\%$ of the testdata, $2 \le b \le 1{,}000$. - For $60\%$ of the testdata, $2 \le b \le 50{,}000{,}000$. - For $100\%$ of the testdata, $2 \le a, b \le 2{,}000{,}000{,}000$. Translated by ChatGPT 5