GCD和LCM

说在前面

其实就是挖一个坑而已,NOIP之前要赶快填上,不能再颓废了。

GCD和LCM

GCD

GCD的原理就是辗转相除法。

其实就是运用到了这是欧几里得算法,和其中一个定理:GCD(x,y)=GCD(y,x%y);

也就是两个数:x和y的最大公约数等于y,x%y这两个数的最大公约数。

证明如下:

a=k*b+r,则r=a-k*b;
a%b=(k*b+r)%b
所以a%b=r;
设d为a和b的公约数。
则 a|d , b|d
因为(a-k*b)|d,所以r|d
以为a%b|d且b|d
所以d为(b,a%b)的公约数
又因为d为(a,b)的公约数
所以GCD(a,b)=GCD(b,a%b);
(所有公约数都相等那么最大公约数必然相等)

1
2
3
4
5
6
7
8
9
10
11
int GCD(int x,int y)
{
int This=x%y;
while(This)
{
x=y;
y=This;
This=x%y;
}
return y;
}

LCM

LCM的原理就是一个公式,LCM*GCD=X*Y

也就是说,最小公倍数乘以最大公约数就等于两个原来的数相乘。

证明如下:

设a=GCD(x,y),则x=n*a,y=m*a;
因为a为最大公约数,所以n和m必定互质。
则n*m*a为x和y的公倍数且一定最小。
所以LCM(x,y)=n*m*a;
则LCM*GCD=n*m*a*a=n*a*m*a=x*y;
所以LCM*GCD=X*Y

1
2
int LCM(int x,int y)
{ return x\*y/GCD(x,y); }

二进制的GCD算法

基本规则:

我们可以使用这种算法来加快GCD的过程,但是最主要的应用就是在高精度GCD的使用上面。

因为高精度膜法并不会写,所以遇到高精度GCD的时候,我们可以转换为折半运算(乘1/2),也就是高精度乘法即可。

规则:

  1. 若a、b都为偶数,则GCD(a,b)=2*GCD(a/2,b/2);
  2. 若a是奇数、b是偶数,则GCD(a,b)=GCD(a,b/2);
  3. 若a是偶数、b是奇数,则GCD(a,b)=GCD(a/2,b);
  4. 若a、b都为奇数,且a-b>=0则GCD(a,b)=GCD(a-b,b);
  5. 若a、b都为奇数,且a-b<=0则GCD(a,b)=GCD(b-a,a);
  • 证明:第一条,若a、b都为偶数,则GCD(a,b)=2*GCD(a/2,b/2);
  1. 设x为GCD(a,b),则 a=n*x,b=m*x;
  2. 因为x为最大公约数,则m和n必定互质。
  3. 则a/2=n*x/2,b/2=m*x/2;
  4. 因为a和b都为偶数,则x必定为偶数。
  5. 所以GCD(a/2,b/2)=x/2;
  6. 则GCD(a,b)=2*GCD(a/2,b/2),证毕。
  • 证明:第二条,若a是奇数、b是偶数,则GCD(a,b)=GCD(a,b/2);
  1. 因为a为奇数,则a和b的最大公约数必定为奇数。
  2. 设x为GCD(a,b),则 a=n*x,b=m*x,则b/2=m*x/2;
  3. 因为x为奇数,b为偶数,则m必定为偶数。
  4. 设k=m/2,则b/2=k*x,a=n*x,且k和m互质。
  5. 所以x=GCD(a,b/2)=GCD(a,b),证毕。
  • 证明:第三条,若a是偶数、b是奇数,则GCD(a,b)=GCD(a/2,b);
  1. 因为b为奇数,则a和b的最大公约数必定为奇数。
  2. 设x为GCD(a,b),则 a=n*x,b=m*x,则a/2=n*x/2;
  3. 因为x为奇数,a为偶数,则n必定为偶数。
  4. 设k=n/2,则a/2=k*x,b=m*x,且k和m互质。
  5. 所以x=GCD(a,b/2)=GCD(a,b),证毕。
  6. (其实证明过程和第二条是一样的)
  • 证明:第四条,若a、b都为奇数,且a-b>=0则GCD(a,b)=GCD(a-b,b);
  1. 设x为GCD(a,b),则a=n*x,b=m*x,且n和m互质。
  2. 则a-b=(n-m)*x,且n-m>=0。则n-m和m互质。
  3. 所以GCD(a,b)=GCD(a-b,b)。证毕。
  • 证明:第五条,若a、b都为奇数,且a-b<=0则GCD(a,b)=GCD(b-a,a);
  1. 设x为GCD(a,b),则a=n*x,b=m*x,且n和m互质。
  2. 则b-a=(m-n)*x,且m-n>=0。则m-n和n互质。
  3. 所以GCD(a,b)=GCD(b-a,a)。证毕。

感觉是伪证啊……

代码实现:

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
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cctype>
#include<algorithm>
using namespace std;
long long a,b;
long long GCD(long long x,long long y)
{
if(!x) return y;
if(!(x&1)&&!(y&1)) return 2\*GCD(x/2,y/2);
if((x&1)&&!(y&1)) return GCD(x,y/2);
if(!(x&1)&&(y&1)) return GCD(x/2,y);
if((x&1)&&(y&1))
{
if(x-y>0) return GCD(x-y,y);
else return GCD(y-x,x);
}
}
int main()
{
cin>>a>>b;
cout<<GCD(a,b)<<endl;;
return 0;
}