份额折算逆数

普及-⏱ 1000ms💾 256MB#P3262🏷️ 扩展欧几里得数论

题目描述

账目折算需要求"折算逆数":给定正整数 $a$ 和 $b$,求最小的正整数 $x$,使得 $ax \equiv 1 \pmod{b}$。数据保证有解(即 $\gcd(a, b) = 1$)。

输入格式

一行两个正整数 $a$ 和 $b$,以空格分隔。

输出格式

一行一个正整数:最小正整数解 $x$。

数据范围

None

样例输入 #1
3 13
样例输出 #1
9
样例输入 #2
7 1000000007
样例输出 #2
142857144