NOIP2012 Day2 T1(求逆元)

求逆元模板。。原方程根据同余定理可化为$ax-1=by$, $y$是一个常数且为整数,移项,$ax-by=1$,题目保证有解,那就不用判断了,直接用exgcd求$ax+by=gcd(a, b)$即可,此时有解那么$gcd(x, y)=1$.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
LL a, b;
LL exgcd(LL a, LL b, LL &x, LL &y) {
if (b == 0) {
x = 1, y = 0;
return a;
}
int ans = exgcd(b, a % b, x, y);
int tmp = x;
x = y, y = tmp - a / b * y;
return ans;
}
void clean() {}
void solve() {
clean();
LL xi ,yi;
exgcd(a, b, xi, yi);
printf("%lld\n", (xi + b) % b);
}
int main() {
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);freopen("1.out", "w", stdout);
#endif
scanf("%lld%lld", &a, &b), solve();
return 0;
}

------ 本文结束 ------