luogu P1082 同余方程

题目描述

求关于方程\(ax \equiv 1 (\mod b)\)的最小整数解

输入

含两个正整数 \(a,b\)用一个空格隔开。

输出

一个正整数\(x\)，即最小正整数解。输入数据保证一定有解。

样例

$in

3 10

\(out\)

7

答题过程：

\[ ax = yb + 1 \\ ax - by = 1 \\ \because gcd(a,b) = 1 \\ \therefore ax + by = gcd(a,b) \]

为什么从减变成加了呢？因为\(y\)是我们随意设的数字，\(y\)可正可负，但是\(a,b\)是不能小于零的。这一点是非常重要的。

代码

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
long long x,y,a,b;

void exgcd(long long a,long long b,long long &x,long long &y){
    if(b == 0){
        x = 1;
        y = 0;
        return;
    }
    exgcd(b,a%b,x,y);
    long long tmp = y;
    y = x - (a/b) * y;
    x = tmp;
    return;
}

int main(){
    cin >> a >> b;
    exgcd(a,b,x,y);
    while(x < 0) x += b;
    cout << x << endl;
    return 0;
}