OpenJudge

2:NOIP2012:同余方程

总时间限制:
1000ms
内存限制:
65536kB
描述

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

输入
输入只有一行,包含两个正整数 a, b,用一个空格隔开。
输出
输出只有一行,包含一个正整数 x0,即最小正整数解。输入数据保证一定有解。
样例输入
3 10
样例输出
7
提示
https://www.luogu.org/problem/show?pid=1082

数据范围】

对于 40%的数据,2 ≤b≤ 1,000;

对于 60%的数据,2 ≤b≤ 50,000,000;

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

NOIP 2012 提高组 第二天 第一题
来源
lbt
全局题号
13772
添加于
2017-03-21
提交次数
5
尝试人数
5
通过人数
5