链接:
https://www.acwing.com/problem/content/205/
题意:
求关于x的同余方程 ax ≡ 1(mod b) 的最小正整数解。
思路:
首先:扩展欧几里得推导.
有ax+by = gcd(a, b) = gcd(b, a%b),
ax+by = bx+(a%b)y
ax+by = bx+(a-(a/b)b)y
ax+by = bx + ay-(a/b)by
ax+by = ay + b(x-a/by)
有x‘ = y, y‘ = x-a/by
递归求解
对于ax = 1 (mod b).有b | ax+1. 令 ax+1 = -yb.
有ax+by = 1.用扩展欧几里得可以求出一个解.
代码:
#include <bits/stdc++.h>
using namespace std;
int ExGcd(int a, int b, int &x, int &y)
{
if (b == 0)
{
x = 1, y = 0;
return a;
}
int d = ExGcd(b, a%b, x, y);
int tmp = y;
y = x-(a/b)*y;
x = tmp;
return d;
}
int main()
{
int a, b, x, y;
scanf("%d%d", &a, &b);
int gcd = ExGcd(a, b, x, y);
printf("%d\n", ((x%b)+b)%b);
return 0;
}