原题链接
更好的阅读体验

题目描述

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

输入格式
输入只有一行，包含两个正整数a,b,用一个空格隔开。

输出格式
输出只有一行,包含一个正整数x，表示最小正整数解。

输入数据保证一定有解。

数据范围
$2 \le a,b \le 2∗10^9$

样例

输入样例：
3 10
输出样例：
7

拓展欧几里得算法+线性同余方程

线性同余方程,也就是给定a,b,m,求一个整数x满足$a \times x \equiv b(mod m)$,然后因为$a \times x \equiv b(mod m)$等价于$a \times x-b$是m的倍数,不妨设y为一个负数,那么这个方程可以改写为$a \times x+m \times y=b$

然后这道题目就是特殊的,$a \times x \equiv 1 (mod b)$

于是我们可以通过拓展欧几里得算法求出特解,然后$(x\%b+b)\%b$来达到最小值的效果.

C++ 代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
inline int ex_gcd(int a,int b,int &x,int &y)
{
    if (b==0)
    {
        x=1;
        y=0;
        return a;
    }
    int d=ex_gcd(b,a%b,x,y);
    int z=x;
    x=y;
    y=z-y*(a/b);
    return d;
}
signed main()
{
    int a,b,x=0,y=0;
    scanf("%lld%lld",&a,&b);
    ex_gcd(a,b,x,y);
    printf("%lld\n",(x%b+b)%b);
    return 0;
}

作者：秦淮岸灯火阑珊
链接：https://www.acwing.com/activity/content/code/content/24474/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。