牛客 同余方程 （数论之扩展欧几里得）

题目描述
求关于x 的同余方程ax ≡ 1 (mod b)的最小正整数解。

输入描述:
输入只有一行，包含两个正整数a,b，用一个空格隔开。
输出描述:
输出只有一行，包含一个正整数x0，即最小正整数解。输入数据保证一定有解。

输入
3 10

输出
7
备注:
对于40%的数据，2≤b≤1,000；
对于60%的数据，2≤b≤50,000,000；
对于100%的数据，2≤a,b≤2,000,000,000。

附上一篇讲解扩展欧几里得算法很清晰的博客扩展欧几里得算法

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 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);
}

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;
}