本文主要是介绍拓展欧几里得求逆元，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

洛谷P1082 [NOIP2012 提高组] 同余方程

 这题不能用费马小定理，b不一定是质数，求逆元是能满足互质条件，但是费马小定理还需要b是质数；

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 ll exgcd(ll &x,ll &y,ll a,ll b)
 5 {
 6     if(!b)
 7     {
 8         x=1,y=0;
 9         return a;
10     }
11     ll p=exgcd(x,y,b,a%b);
12     ll xx=x,yy=y;
13     x=yy;
14     y=xx-(a/b)*yy;
15     return p;
16 }
17 int main()
18 {
19     ll a,b,x=0,y=0;
20     cin>>a>>b;
21     exgcd(x,y,a,b);
22     cout<<(x+b)%b<<endl;//求出来的不一定是最小正整数解，避免出现负值； 
23     return 0;
24  } 

这篇关于拓展欧几里得求逆元的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！