题目链接

传送门

思路

首先我们可以看到这个同余方程\(ax≡1(mod b)\)， 它是可以转化为\(ax+by=1\)的形式的。而题目说保证有解，所以\(gcd(a,b)=1gcd(a,b)=1\)（无解要满足\(gcd(a,b)\)不能整除1）

这题就简单跑一下扩展欧几里得求逆元就ok了

扩展欧几里得求逆元证明

设
\[ax_1 + by_1 = (a,b) \]
\[bx_2 + (a mod b)y 2 = (b,a \mod b)\]
可得:
\[ax_1 + by_1 = (a,b) \]
\[ay_2 + b(x_2 ? ?\frac{a}{b}?y_2 ) = (b,a \mod b) \]
根据欧几里得原理，也就是：
\[(a,b) = (b,a mod b) \]

可以证明:
\[x_1 = y_2 ,y_1 = x_2 ? ? \frac{a}{b}?y_2 \]

注意当 \(b = 0\)时，有 \(x = 1,y = 0\)

代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<map>
#include<string>
#include<cstring>
#define ll long long int
using namespace std;
const int maxn=999999999;
const int minn=-999999999;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}   
void gcd(int a,int b,int &x,int &y)
{
    if(b) gcd(b,a%b,y,x),y-=(a/b)*x;
    else x=1,y=0;
}
signed main()
{
    
    int a,b,x,y;
    cin>>a>>b;
    gcd(a,b,x,y);
    cout<<(x+b)%b;//防止出现负数
    return 0;
}

P1082 同余方程

原文：https://www.cnblogs.com/pyyyyyy/p/10872374.html