同余方程

原题链接：https://www.luogu.org/problem/show?pid=1082#sub

此题乃exgcd的模板题，当然也可以用费马小定理做（赤裸裸的逆元啊）

还记得exgcd是啥吗？扩展欧几里得算法，用来求解形似ax+by = gcd(a,b)一类方程的解。

那和这个题有什么关系啊？这个题要求关于 x 的同余方程 ax ≡ 1 (mod b)的最小正整数解，我们把这个式子展开看一下。

由同余式的意义，可以得知ax % b=1, 1%b =1，可以转化成方程ax+by=1，然后要求这个方程的一组解。

很显然，这个方程代表的是一条直线，满足这个方程的解对应的点都在这条直线上，即有无数个解，我们要找的是最小的正整数解x。

（y到底是多少没必要去关心，我们求的是x，这样等价正好满足扩欧）

同时，这个方程在gcd(a,b)!=1时无解，不过没关系啦，本题保证一定有解。

我们用扩欧求出的解并不一定是最小解，所以输出的时候要对b取模。

负数解怎么办？先加一个b，再对b取模，搞定。

参考代码：

#include <iostream>
using namespace std;
long long int a,b,x,y;
void exgcd(long long int a,long long int b,long long int &x,long long int &y){
    if (!b){
        x = 1;
        y = 0;
    }
    else{
        exgcd(b,a%b,y,x);
        y -= (a/b) * x;
    }
}
int main(){
    cin >> a >> b;
    exgcd(a,b,x,y);
    cout << (x+b) % b << endl;
    return 0;
}