最大公约数，不定方程和同余方程

左手的ㄟ右手 2023-03-04 06:32 32阅读 0赞

# 求解不定方程和同余方程之欧几里得算法 #

1.  计算最大公约数和不定方程
2.  计算同余方程和同余方程组
3.  计算多项式同余方程

### 1.计算最大公约数和同余方程 ###

计算最大公约数常用有辗转相除法或者是欧几里得算法。二者原理基本相似：整数a和整数b的最大公约数通过反复应用除运算，直到余数为零，最后的非零余数就是最大公约数。  
**1.欧几里得算法(辗转相除法)如下：**

void gcd(int a,int b)
    { 
    	if(b==0)
    		return a;
    	else return gcd(b,a%b);
    }

**欧几里得算法数学证明：**  
       欧几里得有个非常强的定理，即gcd(a,b)=gcd(b,a mod b)，让我们来证明一下（mod 是取余，gcd是最大公约数，| 是能整除）  
假设a、b的公约数为k，a = bx + y  
则 k | a，k | b，a mod b=y  
因为 k | b，所以 k |bx，又因为 k | a，所以 k | (a - bx)，即 k | y  
而a mod b = y，所以 k | a mod b  
再假设b、a mod b的公约数为kk，同理得 kk | a，所以（a，b）和（b，a mod b）的公约数是相同的，所以它们的最大公约数也是相同的  
所以gcd(a,b)=gcd(b,a mod b)  
       **时间复杂度O(log n)**  
(讨论情况为a>=b）  
       a mod b必然是小于a/2的，而上一次的b会变成下一次的a，上一次的a mod b会变成下一次的b，最坏情况也就是b在a/2附近，即a mod b在a/2附近。在最坏情况时每次的值也会减少一半，所以说时间复杂度是O（log n）的。（实际中往往会更低）

#### 欧几里得算法扩展应用 ####

**乘法逆元：** 若有 a\*x ≡ 1 （mod m），则称 x 为a关于m的乘法逆元，等价式 a \* x+m \* y = 1。相当于一个二元一次方程  
**如何求解 （以下讨论a>b）**  
显然当 b=0，gcd（a，b）=a。此时 x=1，y=0；  
当a>b>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；（a mod b = a - \[a / b\]\*b；\[a / b\]代表a整除b）  
也就是ax1+ by1 = ay2 + b（x2- \[a / b\] \*y2）；  
根据恒等定理得：x1=y2；y1=x2- \[a / b\] \*y2；  
这样我们就得到了求解 x1，y1 的方法：x1，y1 的值基于 x2，y2  
由引理我们知道：ax+by = z，z为gcd（a，b）若干倍，所以我们先求解ax+by = gcd（a，b），再将求出的解乘以 z/gcd（a，b）就好了。

**扩展欧几里得算法代码：**

void exgcd(int a,int b,int &x,int &y)
    { 
    	if(b==0)
    	{ 
    		x=1;
    		y=0;
    		return a;
    	}
    	int tmp=exgcd(b,a%b,x,y);
        tmp=x; 
        x=y;
        y=tmp-a/b*y;
        return r;
    }
    扩欧算法可用来求解二元一次方程通解（最小）

**2.更相减损方法：**

第一步：任意给定两个正整数；判断它们是否都是偶数。若是，则用2约简；若不是则执行第二步。  
第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止。  
则第一步中约掉的若干个2的积与第二步中等数的乘积就是所求的最大公约数。  
其中所说的“等数”，就是公约数。求“等数”的办法是“更相减损”法。  
       **算法代码**

int gcd(int m,int n)                
    { 
    	int i=0,temp,x;
    	while(m%2==0 && n%2==0)     //判断m和n能被多少个2整除
    	{ 
    		m/=2;
    		n/=2;
    		i+=1;
    	}
    	if(m<n)                       //保存大的值
    	{ 
    		temp=m;
    		m=n;
    		n=temp;
    	}
    	while(x)
    	{ 
    		x=m-n;                     
    		m=(n>x)?n:x;
    		n=(n<x)?n:x;                
    		if(n==(m-n))                
    			break;
    	}
    	if(i==0)
    		return n;
    	else
    		return (int )pow(2,i)*n;
    }
    函数返回值为两个数字的最大公因数

**3.定义法（穷举法、试除法）**  
最麻烦的方法，也称穷举法，从min(m,n)~1中不断试除寻找最大公因数。

int gcd (int m,int n) //自定义函数求两数的最大公约数
    { 
        int  temp;          //定义义整型变量
        temp=(m>n)?m:n;    ///采种条件运算表达式求出两个数中的最小值
        while(temp>0)
        { 
           if (m%temp==0&&n%temp==0) //只要找到一个数能同时被a,b所整除，则中止循环
              break;
           temp--;      //如不满足if条件则变量自减，直到能被a,b所整除
        }
      return temp; //返回最大公因数
    }

以上为三种求解最大公约数的方法，同余方程和不定方程后期赘述。