Preparing NOJ

同余方程

1000ms 131072K

Description:

求关于$$$x$$$的同余方程 $$$ax \equiv 1(mod b)$$$的最小正整数解。

Input:

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

Output:

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

Sample Input:

3 10

Sample Output:

7

Note:

$$$2\le a,b \le 2 000 000 000.$$$

Info

NOJ

Provider NOJ

Code NOJ2347

Tags

Submitted 79

Passed 8

AC Rate 10.13%

Date 03/11/2019 16:03:55

Related

Nothing Yet