题意

给定正整数 $a,b$，求同余方程 $ax\equiv1\pmod b$ 的最小正整数解 $x$。

解析

由于题目没有保证 $b$ 为质数，所以不能用费马小定理，需要使用拓展欧几里得算法求乘法逆元。

前置芝士

$a$ 在模 $b$ 下存在乘法逆元，当且仅当 $\gcd(a,b)=1$。此时存在整数 $x,y$ 使 $a x + b y = 1$（即裴蜀定理）。等式两边同时对 $b$ 取模可得 $a x \equiv 1 \pmod b$，所以该 $x$ 即为所求逆元。

解法

使用扩展欧几里得算法求出一对 $x,y$ 使得 $ax+by=\gcd(a,b)$。由于题目保证有解，即 $\gcd(a,b)=1$，则此时答案为 $(x\bmod b+b)\bmod b$，从而得到最小非负解。

标程

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int extended_gcd(int a,int b,int &x,int &y)//用拓展欧几里得算法求逆元
{
    if(!b) 
    {
        x=1;
        y=0;
        return a;
    }
    int gcd;
    gcd=extended_gcd(b,a%b,y,x);
    y-=(a/b)*x;
    return gcd;
}
inline int inv(int b,int m)//a mod m 意义下的乘法逆元
{
    int x,y;
    int gcd=extended_gcd(b,m,x,y);
    return gcd!=1?-1:(x%m+m)%m;
}
signed main() 
{
    int a,b;
    cin>>a>>b;
    int ans=inv(a,b);
    cout<<ans;
    return 0;
}

时间复杂度

$\mathcal{O}(\log\min(a,b))$。