扩展欧几里得

PS： 算是初次接触数论吧，但是很有意思的是遇到了一个讲解很透彻的博客，几乎把我之前的疑惑都解释清楚了，再次特别感谢那位不知名的博主

1.首先这是一道裸的数论的题目，这个题目有很多地方需要细节处理，第一个就是溢出的问题，因为题目给的数据很大，如果用int去定义的话，两个int变量相乘很可能就会溢出int类型的范围了，（int类型的范围最大是2^31-1，相当于2e9的样子），所以如果担心越界那就用long long去定义变量，那如果非要用int去定义的话，就需要简单的处理一下，我们先让两个变量去相除得到的结果然后再去相乘，这样就解决的越界的问题了

2.题目要求要求最小正整数解，而我们使用这个算法可能会得出负数，为了防止这种情况出现，我们就要在得出结果的时候加上一个整数再去模这个整数，那么就可以得到一个最小正整数解了

3.首先解释一下平时在数学课本上不出现的符号≡，同余符号，含义为两个整数a，b，若它们除以整数m所得的余数相等，则称a，b对于模m同余，记作a≡b(mod m)。那么，同余方程ax ≡ 1 (mod b)，如果转化为我们通俗易懂的语言就是->求满足ax%b=1，1%b=1最小正整数解。
那么接下来就可以使用扩展欧几里得解决了。

AC代码一：

#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 z = x;
   x = y;
   y = z - y * (a / b);
   return d;
}
int main()
{
   int a, b, x, y;
   scanf("%d%d", &a, &b);
   exgcd(a, b, x, y);
   printf("%d\n", (x + b) % b);
   return 0;
}

AC代码二：

#include <bits/stdc++.h>
using namespace std;
int a, b, k, x, y;
void exgcd(int a, int b)
{
    if (b == 0)
    {
        x = 1;
        y = 0;
        return;
    }
    exgcd(b, a % b);
    k = x;
    x = y;
    y = k - a / b * y;
    return;
}
int main()
{
    scanf("%d%d", &a, &b);
    exgcd(a, b);
    printf("%d\n", (x + b) % b);
}