扩展欧几里得算法求乘法逆元

2019-04-14 19:13发布

站内文章 / 模拟电子
14842 0 1604
对于同余方程 ax ≡ 1 (mod b),我们称x为a关于模b的乘法逆元,具体可见百度百科词条“乘法逆元”,那么如何求出最小的正整数x为a关于模b的乘法逆元呢？我们需要用到扩展欧几里得定理算法。由贝祖定理我们知道一定存在一组整数解x,y满足 ax+by=gcd(a,b),而用扩展欧几里得定理我们可以求出一组满足条件的特解。
ax+by=gcd(a,b)=gcd(b,a%b)=bx′+a%b⋅y′=bx′+(a−a/b⋅b)⋅y′=ay′+b(x′−a/b⋅y′)
由此可得
{x=y′y=x′−a/b⋅y′ 于是可以写出代码了 int ext_gcd(int a,int b,int &x,int &y){ if(!b){x=1;y=0;return a;} int tmp=ext_gcd(b,a%b,x,y); int t=x;x=y;y=t-a/b*y; return tmp; } 将 ax ≡ 1 (mod b) 转化一下我们可得ax=by+1=>ax−by=1=>ax+by=1
故我们可以用扩展欧几里得算法求出这里x的特解。于是就成功了！ #include #include #include using namespace std; template <class T> inline void Rd(T &res){ char c;res=0;int k=1; while(c=getchar(),c<48&&c!='-'); if(c=='-'){k=-1;c='0';} do{ res=(res<<3)+(res<<1)+(c^48); }while(c=getchar(),c>=48); res*=k; } int ext_gcd(int a,int b,int &x,int &y){ if(!b){x=1;y=0;return a;} int tmp=ext_gcd(b,a%b,x,y); int t=x;x=y;y=t-a/b*y; return tmp; } int a,b,x,y; int main(){ Rd(a);Rd(b); int tmp=ext_gcd(a,b,x,y); cout<<(x%b+b)%b<return 0; }

热门文章