同余方程（求逆元，线性同余方程最小解

# 题意

给定a，b，求出关于方程ax ≡ 1 (mod b) 的最小x

输入保证了一定有解

2 ≤ a,b ≤ 2*10⁹

# 题解

ax ≡ 1 (mod b)

ax+by=1

通解的表示：

x = x₀ + b * k

y = y₀ - a * k

所以x₀% b就是x能取到的最小值

最后要取正余数常用技巧:模以后加上模的数再模一次

 1 #include<bits/stdc++.h>
 2 #define ll long long
 3 using namespace std;
 4 ll a,b;
 5 ll exgcd(ll a,ll b,ll &x,ll &y){
 6     if(b==0){
 7         x=1;y=0;
 8         return a;
 9     }
10     ll d =exgcd(b,a%b,y,x);
11     y-=a/b*x;
12 }
13 int main(){
14     cin>>a>>b;
15     ll x,y;
16     exgcd(a,b,x,y);
17     cout<<(x%b+b)%b<<endl;
18 }

原文链接: https://www.cnblogs.com/hhyx/p/12640304.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍;

也有高质量的技术群，里面有嵌入式、搜广推等BAT大佬

原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/340361

非原创文章文中已经注明原地址，如有侵权，联系删除

关注公众号【高性能架构探索】，第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处！

同余方程（求逆元，线性同余方程最小解

相关推荐