最大公约数的故事

最大公因数，也称最大公约数、最大公因子，指两个或多个整数共有约数中最大的一个。a，b的最大公约数记为（a，b），同样的，a，b，c的最大公约数记为（a，b，c），多个整数的最大公约数也有同样的记号。——来自《百度百科》

[^]: 两个数的最大公约数a，b一般用gcd（a，b）来表示，因此，我后文也会用gcd（ ， ）来表示两个数的最大公约数

最大公约数在计算机中也很常用，而对于这种数了解最深的非欧几里得莫属了！

欧几里得

欧几里得（英文：Euclid；希腊文：Ευκλειδης，约公元前330年—公元前275年），古希腊人，数学家，被称为“几何之父”。他最著名的著作《几何原本》是欧洲数学的基础，提出五大公设，欧几里得几何，被广泛的认为是历史上最成功的教科书。欧几里得也写了一些关于透视、圆锥曲线、球面几何学及数论的作品。——来自《百度百科》

特别是数论方面有很深的造诣，因此我们今天计算机中关于数论的东西有很可观的一部分来自欧几里得，所以我们在这里看一下最大公约数。

如何算最大公约数？

质因数分解法

这是一个好问题，最简单的方法是用质因数分解法

例如：gcd（24,21）

质因数分解得：

24=2 * 2 * 2 * 3

21=3 * 7

它们公共的因数有3，因此，它们的最大公约数是3；

这个办法我们需要用到质因数分解，质因数分解代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <iostream>
using namespace std;
bool first=true;
void zyz(int n,int p)
{
    if(n>1)
    {
        if(n%p==0)
        {
            if(first)
            {
                cout<<p;
                first=false;
            }
            else cout<<" "<<p;
            zyz(n/p,p);
        }
        else zyz(n/p+1);
    }
}
int main()
{
    int n;
    cin>>n;
    zyz(n,2);
    cout<<endl;
    return 0;
}
//选自信息学奥赛课课通（C++）

更相减损法

但是这样寻找最大公约数太慢了，怎么办呢？

中国古代《九章算术》中有一种方法，称为“更相减损法”

方法是

gcd(a,b)=gcd(b,a−b)gcd(a,b)=gcd(b,a-b)

，这样一直递归下去，当b等于0是，a‘就是a，b的最大公约数。

但这种方法太慢了，有一种更好的方法，我们在下面介绍。

辗转相除法

辗转相除法是欧几里得算法，是求最大公约数最常见的方法，我们来看一看。

我们仔细观察更相减损法，可以发现，gcd（a,b）=gcd(b,a-b)中右边的那一项是一直减b的因此，我们可以联想到计算机中的mod运算(%)，这样效率就大大地加高了。

递推式

gcd(a,b)=gcd(b,a模b)gcd(a,b)=gcd(b,a模b)

所以我们就可以用递归快速求出最大公约数

代码如下

1
2
3
4
int gcd(int a,int b)
{
    return b? gcd(b,a%b):a;
}

这样就完成了求最大公约数

惊现！求逆元！

如果：a×b≡1 (mod n)

那么：

a×m≡a×k (mod n)
=> b×a×m≡b×a×k (mod n)
=> m≡k (mod n)

前提是b存在！

b称为a模n的逆元（a也是b模n的逆元）

x模n的逆元也记作

x−1(mod(n))x^{-1}(mod (n))

——来自wweiyi的暑假集训

这样就可以放心地使用同余中的除法运算了，是不是很帅？？？

因为一个数%n的余数只有可能是0~n-1，又因为0不可能是一个数在模n意义下的逆元，所以我们可以枚举求逆元（From 1 to n-1） 所以，我们可以这样求

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
using namespace std;
int main()
{
    int a,b,n;
    cin>>a>>n;//表示求a在模n意义下的逆元
    for(int i=1;i<=n-1;i++)
    {
        if((a*i)%n==1)
        {
            b=i;break;
        }
    }
    cout<<b<<endl;
    return 0;
}

b就是a在模n意义下的乘法逆元，但是我们看下面一个例子：

例如：11模7的逆元

  	(11,7) 	  (a,b)
  	
  	(7,4) 		(b,a-b)
  	
  	(4,3)         (a-b,2b-a)
  	
  	(3,1)         (2b-a,**2a-3b**)
  	
  	即：2×11-3×7=1
  	
  	2×11≡1 (mod 7)
  	
  	∴11模7的逆元是2

——来自wweiyi暑假集训

有没有发现，这个就是gcd(11,7)的过程，只不过右边用字母代替了它的运算，但实际上是一样的，而到最后一步时，后边加粗的a的系数就是11模7的逆元！是不是很神奇！

所以我们就有了又快又简便的方法来求逆元

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include<bits/stdc++.h>
using namespace std;
int b,x,y,mod,gcd; 
inline int exgcd(int a,int b,int &x,int &y)
{
    if(b==0)
    {
        x=1,y=0;
        return a;
    }
    int ret=exgcd(b,a%b,x,y);
    int t=x;x=y,y=t-(a/b)*y;
    return ret;
}
int main()
{
    cin>>b>>mod;
    gcd=exgcd(b,mod,x,y);
    if(gcd!=1)printf("not exist\n");
    else printf("%d\n",(x%mod+mod)%mod);
    return 0;
}
/*来自 WJEMail大佬
网址:
https://www.cnblogs.com/NSDemail0820/p/9910344.html#_label2
*/

这样我们求出逆元了

神奇！求形如ax+by=c的不定方程整数解和形如ax≡1（mod n）的同余方程

gcd (25,7)

(25,7) (a,b)

(7,4) (b,a-3b)

(4,3) (a-3b,4b-a)

(3,1) (4b-a,2a-7b)

(1,0) (2a-7b,25b-7a)

——来自wweiyi的暑假培训

ax+by=c

也就是使用拓展欧几里得：

扩展欧几里德算法是用来在已知a, b求解一组x，y，使它们满足贝祖等式：

ax+by=gcd(a,b)=dax+by = gcd(a, b) =d

（解一定存在，根据数论中的相关定理）。扩展欧几里德常用在求解模线性方程及方程组中。

——来自《百度百科》

有解的条件：gcd(a,b)|c

因此我们就可以解这样一个方程了!

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>
using namespace std;
int exgcd_x(int c,int d,int x1,int y1,int x2,int y2)
{
	return d?exgcd_x(d,c%d,x2,y2,x1-(c/d)*x2,y1-(c/d)*y2):x1;
}
int exgcd_y(int c,int d,int x1,int y1,int x2,int y2)
{
	return d?exgcd_y(d,c%d,x2,y2,x1-(c/d)*x2,y1-(c/d)*y2):y1;
}
int gcd(int c,int d)
{
	return d?gcd(d,c%d):c;
}
int main()
{
	int a,b,n;
	int x1=1,y1=0,x2=0,y2=1;
	cin>>a>>b>>n;
	if(n%gcd(a,b)!=0)
	{
		cout<<"No solution"<<endl;
		return 0;
	}
	int x=exgcd_x(a,b,x1,y1,x2,y2);
	int y=exgcd_y(a,b,x1,y1,x2,y2);
	int g=n/gcd(a,b);
	cout<<x*g<<"a"<<y*g<<"b="<<n<<endl;
	return 0;
}

ax≡1(mod n)

实际上就是求逆元！

这里就不再多说了!

总结：这个欧几里得算法和拓展欧几里得算法是很有用的算法，我们会很常用，因此我们要熟悉掌握这个算法，在OI竞赛中帮助我们，今天就到这里了