#1039. [NOIP 2012 提高组] 同余方程

[NOIP 2012 提高组] 同余方程

题目描述

求关于 x x 的同余方程 ax≡1(modb) a x \equiv 1 \pmod {b} 的最小正整数解。

输入格式

一行,包含两个整数 a,ba,b,用一个空格隔开。

输出格式

一个整数 x0x_0,即最小正整数解。输入数据保证一定有解。

样例

3 10
7

题目来源:洛谷 P1082