题目地址：

https://www.luogu.com.cn/problem/P1082

题目描述：
求关于$x$的同余方程$ax\equiv 1(\mathrm{mod}b)$的最小正整数解。

输入格式：
一行，包含两个正整数$a,b$，用一个空格隔开。

输出格式：
一个正整数$x_0$，即最小正整数解。输入数据保证一定有解。

数据范围：
对于$40\%$的数据，$2\le b\le 1,000$；
对于$60\%$的数据，$2\le b\le 50,000,000$；
对于$100\%$的数据，$2\le a,b\le 2,000,000,000$。

即求解$ax+by=1$的所有解$(x,y)$中$x$最小正整数可以是多少。可以用扩展欧几里得算法求出一组解$(x_0,y_0)$，则所有解为$(x_0+kb,y_0-ka)$，那么$x$可以取到的最小正整数就是$x$在模$b$剩余类里最小正代表元。代码如下：

#include 
using namespace std;

long a, b;

long exgcd(long a, long b, long& x, long& y) {
  if (!b) {
    x = 1, y = 0;
    return a;
  }

  long d = exgcd(b, a % b, y, x);
  y -= a / b * x;
  return d;
}

int main() {
  scanf("%ld%ld", &a, &b);
  long x, y;
  exgcd(a, b, x, y);
  x = (x % b + b) % b;
  printf("%ld\n", x);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

时空复杂度 O ( log ⁡ min ⁡ { a , b } ) O(\log\min\{a,b\}) O(logmin{a,b})。