说在前面

其实就是挖一个坑而已，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;
}