题目
求关于x的同余方程 ax ≡ 1(mod b) 的最小正整数解。
输入格式 输入只有一行，包含两个正整数a,b,用一个空格隔开。
输出格式 输出只有一行,包含一个正整数x，表示最小正整数解。
输入数据保证一定有解。
数据范围 2≤a,b≤2∗109 输入样例： 3 10 输出样例： 7
思路
本题求线性同余方程，那么只要用扩展欧几里得算法求出特解，之后用(x % b + b) % b 求最小解即可
代码
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std
;
typedef long long LL
;
int exgcd(int a
, int b
, int &x
, int &y
)
{
if (!b
)
{
x
= 1, y
= 0;
return a
;
}
int d
= exgcd(b
, a
% b
, y
, x
);
y
-= a
/ b
* x
;
return d
;
}
int main()
{
int a
, b
;
cin
>> a
>> b
;
int x
, y
;
exgcd(a
, b
, x
, y
);
cout
<< (x
% b
+ b
) % b
<< endl
;
return 0;
}
