ACM 进阶学习第一课----同余相关之欧几里得算法及其扩展（2）

柔光的暖阳◎ 2022-05-12 23:58 138阅读 0赞

# 最大公约数算法分析 #

## 欧几里德算法 ##

伪代码

**while b>0  
do r←a%b  
a←b  
b←r  
return a**

**算法分析：**

欧几里德算法是计算最大公约数的传统算法,也是最简单的算法,效率很高  
时间复杂度:O(lgn)(最坏情况:斐波那契数列相邻的两项)  
空间复杂度:O(1)  
**但是,对于大整数来说,取模运算非常耗时**

## **Stein算法** ##

**伪代码：**

Stein算法(假设0<=b<a):  
r←0  
while b>0  
do if a偶,b偶 then a←a>>1 b←b>>1 r←r+1  
else if a偶,b奇 then a←a>>1  
else if a奇,b偶 then b←b>>1  
else if a奇,b奇 then a←(a-b)>>1  
if a<b then 交换a,b  
return a<<r

**算法分析**

渐近时间,空间复杂度均与欧几里德算法相同  
原理:gcd(ka,kb)=k\*gcd(a,b)  
最大特点:只有移位和加减法计算,避免了大整数的取模运算

代码：

unsigned MaxDivisor(unsigned a, unsigned b) 
    { 
        unsigned c = 0; 
        while(1)
        { 
        // 退出条件 
            if(a==0) 
                return b << c;
            else if(b == 0) 
                return a << c;
        // 为提高速度，采用位的与运算，避免用取模判断奇偶 
            if(!(a & 1) && !(b & 1)) //a,b 都是偶数 
            { 
                a >>= 1; b >>= 1; ++c; 
            } 
            else if(!(a & 1) && (b & 1)) //a偶 b奇 
            { 
                a >>= 1; 
            } 
            else if((a & 1) && !(b & 1)) //a奇 b偶 
            {
                 b >>= 1; 
            } 
            else if((a & 1) && (b & 1)) //a,b都是奇数 
            { 
                unsigned tmp = a>b?b:a; //取较小的一个 
                a = a>b?a-b:(b-a); //绝对差值
                b = tmp; 
            } 
        }
    }

# **扩展欧几里德算法** #

基本算法

对于不完全为 0 的非负整数 a，b，gcd（a，b）表示 a，b 的最大公约数，必然存在整数对 x，y ，使得 gcd（a，b）=ax+by。

【证明】

设 a>b

1，显然当 b=0，gcd（a，b）=a。此时 x=1，y=0；  
2，ab!=0 时  
设 :ax1+by1=gcd(a,b);  
显然也有：bx2+(a mod b)y2=gcd(b,a mod b);  
根据朴素的欧几里德 原理有 gcd(a,b)=gcd(b,a mod b);  
则:ax1+by1=bx2+(a mod b)y2;

即:**ax1+by1=bx2+(a-(a/b)\*b)y2=ay2+bx2-(a/b)\*by2;**

根据恒等定理得：**x1=y2; y1=x2-(a/b)\*y2;**

这样我们就得到了求解 x1,y1 的方法：x1，y1 的值基于 x2，y2.

上面的思想是以递归定义的，因为 gcd 不断的递归求解**一定会有个时候 b=0**，所以递归可以结束。

扩展欧几里得递归代码：

int exgcd(int a,int b,int &x,int &y)
    {
        if(b==0)
        {
            x=1;
            y=0;
            return a;
        }
        int r=exgcd(b,a%b,x,y);
        int t=x;
        x=y;
        y=t-a/b*y;
        return r;
    }

非递归代码：

int exgcd(int m,int n,int &x,int &y)
    {
        int x1,y1,x0,y0;
        x0=1; y0=0;
        x1=0; y1=1;
        x=0; y=1;
        int r=m%n;
        int q=(m-r)/n;
        while(r)
        {
            x=x0-q*x1; y=y0-q*y1;
            x0=x1; y0=y1;
            x1=x; y1=y;
            m=n; n=r; r=m%n;
            q=(m-r)/n;
        }
        return n;
    }

## 应用 ##

扩展欧几里德算法的应用主要有以下三方面：

（1）求解不定方程；

（2）求解模线性方程（线性同余方程）；

（3）求解模的逆元；

#### （1）使用扩展欧几里德算法解决不定方程的办法： ####

对于不定整数方程pa+qb=c，若 c mod Gcd(p, q)=0,则该方程存在整数解，否则不存在整数解。  
上面已经列出找一个整数解的方法，在找到p \* a+q \* b = Gcd(p, q)的一组解p0,q0后，p \* a+q \* b = Gcd(p, q)的其他整数解满足：  
 p = p0 + b/Gcd(p, q) \* t  
q = q0 - a/Gcd(p, q) \* t(其中t为任意整数)  
至于pa+qb=c的整数解，只需将p \* a+q \* b = Gcd(p, q)的每个解乘上 c/Gcd(p, q) 即可。

在找到p \* a+q \* b = Gcd(a, b)的一组解p0,q0后，应该是得到p \* a+q \* b = c的一组解p1 = p0\*(c/Gcd(a,b)),q1 = q0\*(c/Gcd(a,b))，

p \* a+q \* b = c的其他整数解满足：

p = p1 + b/Gcd(a, b) \* t

q = q1 - a/Gcd(a, b) \* t(其中t为任意整数)

p 、q就是p \* a+q \* b = c的所有整数解。

相关证明可参考：[http://www.cnblogs.com/void/archive/2011/04/18/2020357.html][http_www.cnblogs.com_void_archive_2011_04_18_2020357.html]

用扩展欧几里得算法解不定方程ax+by=c;

代码如下：

bool linear_equation(int a,int b,int c,int &x,int &y)
    {
        int d=exgcd(a,b,x,y);
        if(c%d)
            return false;
        int k=c/d;
        x*=k; y*=k;    //求得的只是其中一组解
        return true;
    }

#### (2)用扩展欧几里德算法求解模线性方程的方法： ####

**同余方程ax≡b (mod n)对于未知数 x 有解，当且仅当 gcd(a,n) | b。且方程有解时，方程有 gcd(a,n) 个解。**

求解方程 ax≡b (mod n)相当于求解方程 ax+ ny= b, (x, y为整数)

设 d= gcd(a,n)，假如整数 x 和 y，满足 d= ax+ ny(用扩展欧几里德得出)。如果 d| b，则方程

a\* x0+ n\* y0= d， 方程两边乘以 b/ d，(因为 d|b，所以能够整除)，得到 a\* x0\* b/ d+ n\* y0\* b/ d= b。  
所以 x= x0\* b/ d，y= y0\* b/ d 为 ax+ ny= b 的一个解，所以 x= x0\* b/ d 为 ax= b (mod n ) 的解。

ax≡b (mod n)的一个解为 x0= x\* (b/ d ) mod n，且方程的 d 个解分别为 xi= (x0+ i\* (n/ d ))mod n \{i= 0... d-1\}。

设ans=x\*(b/d),s=n/d;

方程ax≡b (mod n)的最小整数解为：(ans%s+s)%s;