[LOJ2605] 同余方程

Description

求同余方程 (ax equiv 1 (mod b)) 的最小正整数解。

Solution

转化为求解方程 (ax+by equiv 1 (mod b)) 的 (x) 的最小正整数解。

我们可以先暴力用 exgcd 解出 (x)，然后令 (x=(x+b) mod b) 即可。

#include <bits/stdc++.h>
using namespace std;

#define int long long 
const int N = 1000005;

int a,b;

inline void exgcd(int a,int b,int &x,int &y) 
{
    if(!b) 
    {
        x=1,y=0;
        return;
    }
    exgcd(b,a%b,x,y);
    int t=x;
    x=y,y=t-(a/b)*y;
}

signed main()
{
    ios::sync_with_stdio(false);

    cin>>a>>b;
    int x,y;
    exgcd(a,b,x,y);
    x=(x+b)%b;
    cout<<x<<endl;

    system("pause");
}