UOJ Logo 小司码 Online Judge

XSMOJ

第637题   同余方程

统计 下一题 上一题

题目描述

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

输入格式

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

输出格式

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

样例数据

input

3 10

output

7

数据规模与约定

时间限制:$1 \text{s}$

空间限制:$256 \text{MB}$