比赛场次	291
比赛名称	20160303
比赛状态	已结束比赛成绩
开始时间	2016-03-03 19:00:00
结束时间	2016-03-03 22:00:00
开放分组	全部用户
注释介绍

题目名称	同余方程
输入输出	`mod.in/out`
时间限制	1000 ms (1 s)
内存限制	128 MiB
测试点数	10 简单对比

用户	结果	时间	内存	得分
1azyReaper	AAAAAAAAAA	0.001 s	0.32 MiB	100
Fancy	AAAAAAAAAA	0.002 s	0.29 MiB	100
农场主	AAAAAAAAAA	0.002 s	0.29 MiB	100
mikumikumi	AAAAAAAAAA	0.002 s	0.31 MiB	100
haah	AAAAAAAAAA	0.002 s	0.31 MiB	100
NVIDIA	AAAAAAAAAA	0.003 s	0.31 MiB	100
Rapiz	AAAAAAAAAA	0.006 s	0.29 MiB	100
Twist Fate	AAAAAAATTT	3.740 s	0.15 MiB	70
KZNS	WAAAWWWAAA	0.001 s	0.31 MiB	60
小明		0.000 s	0.00 MiB	0

同余方程

★☆ 输入文件：mod.in 输出文件：mod.out 简单对比
时间限制：1 s 内存限制：128 MiB

【题目描述】

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

【输入格式】

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

【输出格式】

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

【样例输入】

3 10

【样例输出】

【数据范围】

对于 40% 的数据，$2≤b≤1,000$；

对于 60% 的数据，$2≤b≤50,000,000$；

对于 100% 的数据，$2≤a,b≤2,000,000,000$。