同余方程

题意描述

求关于 的同余方程的最小正整数解，若无解，输出"-1"

思路

实际上就是求a的逆元 有这样几种方法

1. 费马小定理
2. 解不定方程
3. 欧拉定理 , 那么 一定是a的逆元 但是费马小定理和欧拉定理求出来的不一定是最小的正整数解，所以我们考虑用"解不定方程"

解不定方程

1. 可以转换为 , 求解就好了
2. 但是求出来的只是其中一组解，我们要求出来最小的那一组才行
3. 假设求出来的一组解是， 那通解就是 ,
4. 要求最小的, 考虑让,为了方便，让， 那么
5. 代回去，, 发现这个东西不就是 % 吗

代码

#include <bits/stdc++.h>
#define endl '\n'
using lli = long long;

lli exgcd(int a, int b, int &x, int &y)
{
    if (b == 0)
    {
        x = 1, y = 0;
        return a;
    }
    lli r = exgcd(b, a % b, x, y);
    std::tie(x, y) = std::make_tuple(y, x - (a / b) * y);
    return r;
}

int main()
{
    int a = 0, b = 0, x = 0, y = 0;
    std::cin >> a >> b;
    lli r = exgcd(a, b, x, y);
    if (r != 1)
    {
        std::cout << -1 << endl;
    }
    else
    {
        int tmp = abs(a / r);
        std::cout << (x % tmp + tmp) % tmp << endl;
    }
    return 0;
}