#NOIPS2012D. 同余方程 (Congruence Equation)

同余方程 (Congruence Equation)

题目描述

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

输入格式

输入只有一行,包含两个正整数 a,ba, b,用一个空格隔开。

输出格式

输出只有一行,包含一个正整数 x0x_0,即最小正整数解。输入数据保证一定有解。

3 10
7

数据范围与提示

对于 40%40\% 的数据,有 2b1032 \leq b \leq 10^3
对于 60%60\% 的数据,有 2b5×1072 \leq b \leq 5\times 10^7
对于 100%100\% 的数据,有 2a,b2×1092 \leq a, b \leq 2\times 10^9