问题 F: 同余方程
内存限制:128 MB
时间限制:1.000 S
评测方式:文本比较
命题人:
提交:21
解决:17
题目描述
求关于x的同余方程ax≡1(modb)的最小正整数解。
输入
输入只有一行,包含两个正整数a,b,用一个空格隔开。
输出
输出只有一行,包含一个正整数x0,即最小正整数解。输入数据保证一定有解。
样例输入 复制
3 10
样例输出 复制
7
提示
对于40%的数据,有2≤b≤1000;
对于60%的数据,有2≤b≤50000000;
对于100%的数据,有2≤a,b≤2000000000。
对于60%的数据,有2≤b≤50000000;
对于100%的数据,有2≤a,b≤2000000000。