题解 P1082 【同余方程】

alan20050721 · 2019-03-09 20:00:28 · 题解

刚学拓展欧几里得的同学，

看下这个有好处。

就是这个当然，看不懂的话也可以直接背板子

先分析题目：

ax ≡ 1(mod b) ,根据同余定义，那么：

ax+by=1(其中x为要求解)

此时，题目变成了求二元一次不定方程最小解的题

套板子吧。

详见代码

#include <bits/stdc++.h>
using namespace std;
#define int long long    //不用longlong要炸
int extgcd(int a, int b, int &x, int &y) {
    int d, t;
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    d = extgcd(b, a%b, x, y);
    t = x - a / b * y;
    x = y;
    y = t;
    return d;
}
signed main() {
    int a, b, x, y, d;
    cin >> a >> b;
    d = extgcd(a, b, x, y);//拓展欧几里得
    int r = b / d;
    cout << (x%r + r) % r; //最大正整数解
    return 0;
}