＜蓝桥杯软件赛＞零基础备赛20周--第16周--GCD和LCM

报名明年4月蓝桥杯软件赛的同学们，如果你是大一零基础，目前懵懂中，不知该怎么办，可以看看本博客系列：备赛20周合集
20周的完整安排请点击：20周计划
每周发1个博客，共20周。
在QQ群上交流答疑：

第16周: ?GCD和LCM
??最大公约数（GCD）和最小公倍数（Least Common Multiple，LCM）研究整除的性质，非常古老，2000多年前就得到了很好的研究。由于简单易懂，有较广泛的应用，是竞赛中频繁出现的考点。
最大公约数有多种英文表述：Greatest Common Divisor(GCD)、Greatest Common Denominator、Greatest Common Factor(GCF)、Highest Common Factor (HCF)。

1. GCD

1.1 GCD概念

?? 整数a和b的最大公约数是能同时整除a和b的最大整数，记为gcd(a, b)。
??负整数也可以算gcd，不过由于-a的因子和a的因子相同，编码时只需要关注正整数的最大公约数。下面用c++函数std::__gcd(a, b)演示gcd的计算结果。

#include<bits/stdc++.h>
using namespace std;
int main(){
    cout << __gcd(45,9)   <<"\n";   // 9
    cout << __gcd(0,42)   <<"\n";   // 42
    cout << __gcd(42,0)   <<"\n";   // 42
    cout << __gcd(0,0)    <<"\n";   // 0
    cout << __gcd(20,15)  <<"\n";   // 5
    cout << __gcd(-20,15) <<"\n";   // -5
    cout << __gcd(20,-15) <<"\n";   // 5
    cout << __gcd(-20,-15)<<"\n";   // -5
    cout << __gcd((long long)98938441343232,(long long)33422)<<"\n"; //2
}

??Java没有自带GCD库函数。
??Python自带的GCD函数，只返回正整数。

from  math import *
print(gcd(45, 9))                # 9
print(gcd(0, 42))                # 42
print(gcd(42, 0))                # 42
print(gcd(0, 0))                 # 0
print(gcd(20, 15))               # 5
print(gcd(-20, 15))              # 5
print(gcd(20, -15))              # 5
print(gcd(-20, -15))             # 5
print(gcd(98938441343232, 33422)) # 2

1.2 GCD性质

??GCD有关的题目一般会考核GCD的性质。
??（1）gcd(a, b) = gcd(a, a+b) = gcd(a, k·a+b)
??（2）gcd(ka, kb) = k·gcd(a, b)
??（3）多个整数的最大公约数：gcd(a, b, c) = gcd(gcd(a, b), c)。
??（4）若gcd(a, b) = d，则gcd(a/d, b/d) = 1，即a/d与b/d互素。这个定理很重要。
??（5）gcd(a+cb, b) = gcd(a, b)

1.2 GCD编码实现

?? 编程时可以不用自己写GCD代码，而是直接使用c++函数std::__gcd(a, b)。如果自己编码也很简单，用欧几里得算法，又称为辗转相除法，即gcd(a, b) = gcd(b, a mod b)。

int gcd(int a, int b){        // 一般要求a>=0, b>0。若a=b=0，代码也正确，返回0
	return b? gcd(b, a%b):a;
}

??Java的gcd需要自己写。

import java.math.BigInteger;
public class Main {
    public static void main(String[] args) {
        System.out.println(gcd(45, 9));                // 9
        System.out.println(gcd(0, 42));                // 42
        System.out.println(gcd(42, 0));                // 42
        System.out.println(gcd(0, 0));                 // 0
        System.out.println(gcd(20, 15));               // 5
        System.out.println(gcd(-20, 15));              // -5
        System.out.println(gcd(20, -15));              // 5
        System.out.println(gcd(-20, -15));             // -5
        System.out.println(gcd(new BigInteger("98938441343232"), new BigInteger("33422"))); // 2
    }
    public static long gcd(long a, long b) {
        if (b == 0)   return a;        
        return gcd(b, a % b);
    }
    public static BigInteger gcd(BigInteger a, BigInteger b) {
        return a.gcd(b);
    }
}

??python。自己写gcd()函数，可能返回负数。

def gcd(a,b):
    if b ==0:return a
    else: return gcd(b,a%b)
print(gcd(45, 9))                # 9
print(gcd(0, 42))                # 42
print(gcd(42, 0))                # 42
print(gcd(0, 0))                 # 0
print(gcd(20, 15))               # 5
print(gcd(-20, 15))              # 5
print(gcd(20, -15))              # -5
print(gcd(-20, -15))             # -5
print(gcd(98938441343232, 33422)) # 2

2. LCM

?? 最小公倍数LCM（the Least Common Multiple）。a和b的最小公倍数lcm(a, b)，从算术基本定理推理得到。
??算术基本定理：任何大于1的正整数n都可以唯一分解为有限个素数的乘积：$n=p_1^{c1}{p}_2^{c2}...p_m^{cm}$，其中ci都是正整数，$p_i$都是素数且从小到大。
??设：$a=p_1^{c1}{p}_2^{c2}...p_m^{cm}，b=p_1^{f1}{p}_2^{f2}...p_m^{fm}$
??那么：
???? g c d ( a , b ) = p 1 m i n { c 1 , f 1 } p 2 m i n { c 2 , f 2 } . . . p m m i n { c m , f m } gcd(a, b) = p_1^{min\{c1,f1\}}p_2^{min\{c2,f2\}}...p_m^{min\{cm,fm\}} gcd(a,b)=p1min{c1,f1}?p2min{c2,f2}?...pmmin{cm,fm}?，
???? l c m ( a , b ) = p 1 m a x { c 1 , f 1 } p 2 m a x { c 2 , f 2 } . . . p m m a x { c m , f m } lcm(a, b) = p_1^{max\{c1,f1\}}p_2^{max\{c2,f2\}}...p_m^{max\{cm,fm\}} lcm(a,b)=p1max{c1,f1}?p2max{c2,f2}?...pmmax{cm,fm}?
??可以推出：
????$gcd(a,b)?lcm(a,b)=a?b$
??即
????$lcm(a,b)=a?b/gcd(a,b)=a/gcd(a,b)?b$

c++代码

int lcm(int a, int b){          //需要的时候把int改成long long
	return a / gcd(a, b) * b;  //先做除法再做乘法，防止先做乘法溢出
}

java代码

    public static int gcd(int a, int b) {
        if (b == 0)        return a;        
        return gcd(b, a % b);
    }
    public static long lcm(int a, int b) {
        return (long) a / gcd(a, b) * b;
    }

python代码
??在Python新版本中有库函数lcm()，它可以带多个参数。

from  math import *
print(lcm(3,6,8,9))  #输出72

??也可以自己写一个：

from  math import *
def lcm(x,y):   return x//gcd(x,y)*y

3. 例题

??GCD和LCM的题目太多了，随便到哪个OJ都能以GCD为算法关键词搜出很多。

3.1 等差数列

---

等差数列
【题目描述】数学老师给小明出了一道等差数列求和的题目。但是粗心的小明忘记了一部分的数列，只记得其中N个整数。现在给出这N个整数，小明想知道包含这N个整数的最短的等差数列有几项?
【输入描述】输入的第一行包含一个整数N。 第二行包含N个整数A1,A2,···,AN。(注意A1 ～AN并不一定是按等差数列中的顺序给出) (对于所有评测用例，2≤N≤100000，0≤Ai≤$10^9$。)
【输出描述】输出一个整数表示答案

---

??所有数字间距离最小的间隔是公差吗？ 并不是，例如{2，5，7}，最小的间隔是2，但公差不是2，是1。
??这是gcd问题。把n个数据排序，计算它们的间隔，对所有间隔做GCD，结果为公差。最少数量等于：（最大值-最小值）/公差+1。
c++代码

#include<bits/stdc++.h>
using namespace std;
int a[100000];
int main(){
    int n;   cin>>n;
    for(int i=0;i<n;i++)   cin>>a[i];
    sort(a,a+n);
    int d=0;
    for(int i=1;i<n;i++)   d = __gcd(d,a[i]-a[i-1]);     
    if(d==0) cout<<n<<endl;
    else     printf("%d\n",(a[n - 1] - a[0]) / d + 1);
    return 0;
}

Java代码

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++)  a[i] = sc.nextInt(); 
        Arrays.sort(a);
        int d = 0;
        for (int i = 1; i < n; i++)  d = gcd(d, a[i] - a[i - 1]);        
        if (d == 0)    System.out.println(n);
        else     System.out.println((a[n - 1] - a[0]) / d + 1);        
    }

    public static int gcd(int a, int b) {
        if (b == 0)  return a;        
        return gcd(b, a % b);
    }
}

python代码

from  math import *
n=int(input())
a=list(map(int,input().split()))
a.sort()
d=0
for i in range(1,n):  d=gcd(d,a[i]-a[i-1])
if d==0:  print(n)
else:     print((a[-1]-a[0])//d+1)

3.2 Hankson的趣味题

---

Hankson的趣味题
【题目描述】刚刚放学回家的Hankson正在思考一个有趣的问题。今天在课堂上，老师讲解了如何求两个正整数c1和c2的最大公约数和最小公倍数。现在Hankson认为自己已经熟练地掌握了这些知识，他开始思考一个“求公约数”和“求公倍数”之类问题的“逆问题”，这个问题是这样的：已知正整数a0,a1,b0,b1，设某未知正整数x满足:

1. x和a0 的最大公约数是a1；
2. x和b0的最小公倍数是b1。
   Hankson的“逆问题”就是求出满足条件的正整数x。但稍加思索之后，他发现这样的x并不唯一，甚至可能不存在。因此他转而开始考虑如何求解满足条件的x的个数。请你帮助他编程求解这个问题。
   【输入格式】输入第一行为一个正整数n，表示有n组输入数据。 接下来的n行每行一组输入数据，为四个正整数a0，a1，b0，b1，每两个整数之间用一个空格隔开。输入数据保证a0能被a1整除，b1能被b0整除。
   数据规模：对于100%的数据，保证有1≤a0，a1，b0，b1≤2,000,000,000且n≤2000。
   【输出格式】输出共n行。每组输入数据的输出结果占一行，为一个整数。对于每组数据：若不存在这样的x，请输出0；若存在这样的x，请输出满足条件的x的个数。

---

??最简单的暴力法，是把所有可能的x试一遍。x的范围是x ≤ b1。
??但是，由于本题的数据范围是$b1\le 2\times 10^9$，肯定超时。
??若x是b1的因子，那么x*y = b1，y也可能是答案。所以只需要在范围x<=sqrt(b1)内查询，同时判断y就行了。
??但是这样还是超时，因为gcd计算也要花时间，最后加上一个优化：if(b1%x==0)，表示b1是x的公倍数。

c++代码

#include<bits/stdc++.h>
using namespace std;
int lcm(int a, int b){ return a / __gcd(a, b) * b;}
int main() {
    int n; scanf("%d",&n);
    while(n--) {
        int a0,a1,b0,b1;
        cin >>a0>>a1>>b0>>b1;
        int ans=0;
        for(int x=1;x <= sqrt(b1);x++){
            if(b1%x == 0){        //优化
                if(__gcd(x,a0)==a1 && lcm(x,b0)==b1)  ans++;
                int y = b1/x;       //另外一个因子
                if(x==y) continue;
                if(__gcd(y,a0)==a1 && lcm(y,b0)==b1)  ans++;
            }
        }
        cout << ans <<endl;
    }
    return 0;
}

java

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        while (n-- > 0) {
            int a0 = sc.nextInt();
            int a1 = sc.nextInt();
            int b0 = sc.nextInt();
            int b1 = sc.nextInt();
            int ans = 0;
            for (int x = 1; x <= Math.sqrt(b1); x++) {
                if (b1 % x == 0) {
                    if (gcd(x, a0) == a1 && lcm(x, b0) == b1)   ans++;                    
                    int y = b1 / x;
                    if (x == y) continue;                    
                    if (gcd(y, a0) == a1 && lcm(y, b0) == b1)    ans++;                    
                }
            }
            System.out.println(ans);
        }
    }
    public static int gcd(int a, int b) {
        if (b == 0) return a;        
        return gcd(b, a % b);
    }

    public static int lcm(int a, int b) {
        return a / gcd(a, b) * b;
    }
}

python

from  math import *
def lcm(x,y):  return x//gcd(x,y)*y
n=int(input())
for _ in range(n):
    a0,a1,b0,b1 = map(int,input().split())
    ans=0
    for x in range(1,int(sqrt(b1))+1):
        if b1 % x == 0:
            if gcd(x,a0)==a1 and lcm(x,b0)==b1: ans+=1
            y = b1//x
            if x==y: continue
            if gcd(y,a0)==a1 and lcm(y,b0)==b1: ans+=1
    print(ans)

3.3 最大比例

---

最大比例
【题目描述】X星球的某个大奖赛设了M级奖励。每个级别的奖金是一个正整数。并且，相邻的两个级别间的比例是个固定值。也就是说：所有级别的奖金数构成了一个等比数列。比如：16,24,36,54
其等比值为：3/2
现在，我们随机调查了一些获奖者的奖金数。请你据此推算可能的最大的等比值。
【输入格式】第一行为数字 N (0<N<100)，表示接下的一行包含N个正整数。第二行N个正整数Xi(Xi<1 000 000 000 000)，用空格分开。每个整数表示调查到的某人的奖金数额。
【输出格式】一个形如A/B的分数，要求A、B互质。表示可能的最大比例系数。
测试数据保证了输入格式正确，并且最大比例是存在的。

---

??先试试暴力法。
??把这些数字排个序，然后算出相邻两个数的比值。最小的那个比值K是否就是答案呢？
??不是。例如{2, 16, 64}，比值是16/2=8，64/16=4，最小比值K=4。但是原序列是{2, 4, 8, 16, 32, 64}，比值是2。
??所以答案肯定比K小，如何求出答案？如果一个个试比K小的分数，肯定会超时。
??再用另一个思路，这次不是算相邻两个数的比值，而是每个数对第一个数的比值，会不会好些？
??设原序列是$x,x{q}^1,x{q}^2,...,x{q}^{n?1}$，从中挑出一些数字$x{q}^c,x{q}^d,...,x{q}^y,x{q}^z$，它们之间的两两相除，得到一个比值序列$1,q^{d?c},...,q^{z?y}$，这其中的一些数字可能是相同的，有点麻烦。
??或者算它们对第一个数的比值，得$1,q^{d?c},...,q^{y?c},q^{z?c}=1,q^{kd},...,q^{ky},q^{kz}$ ，这个序列内的所有数字肯定不同。令$q=a/b$，那么这个序列变成了$1,(a/b{)}^{kd},...,(a/b{)}^{ky},(a/b{)}^{kz}$。分成分子和分母两个序列，分别是$A=a^{kd},...,a^{ky},a^{kz},B=b^{kd},...,b^{ky},b^{kz}$。
??已知这两个序列A、B中每个元素的值，求a和b。
??例如A={16, 128, 512, 1024}，得a=2，即$A=2^4,2^7,2^9,2^{10}$。如何根据A求a？
??显然，A中每个数除以前面一个数，都能够整除，得到a的一个倍数，但是这个倍数还不是a，需要继续除，直到得到a为止。以前2个数$2^4,2^7$为例，计算步骤是：$2^7/2^4=2^3，2^4/2^3=2^1，2^3/2^1=2^2，2^2/2^1=2，2^1/2^1=1$，结束，得a=2。这是一个辗转相除的过程。
??对A中所有元素都执行这个过程，就得到了a。下面代码中的gcd_sub()完成了这一任务。

c++代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 105;
ll x[N],a[N],b[N];
ll gcd_sub(ll a,ll b){
    if(a<b)   swap(a,b);
    if(b==1)  return a;
    return gcd_sub(b,a/b);
}
int main(){
    int n; cin >>n;
    ll cnt=0;
    for(int i=0;i<n;i++)  cin>>x[i];
    sort(x,x+n);         //排序
    for(int i=1;i<n;i++){
        ll d = __gcd(x[i],x[0]);
        a[cnt] = x[i]/d;
        b[cnt] = x[0]/d;   //约分,得分子a / 分母b
        cnt++;
    }
    ll up = a[0], down = b[0];
    for(int i=1;i<cnt;i++){
        up= gcd_sub(up,a[i]);        //求分子
        down = gcd_sub(down,b[i]);   //求分母
    }
    cout<<up<<'/'<<down<<endl;
    return 0;
}

java

import java.util.Arrays;
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long[] x = new long[n];
        for (int i = 0; i < n; i++)   x[i] = sc.nextLong();        
        Arrays.sort(x);
        long[] a = new long[n - 1];
        long[] b = new long[n - 1];
        int cnt = 0;
        for (int i = 1; i < n; i++) {
            long d = gcd(x[i], x[0]);
            a[cnt] = x[i] / d;
            b[cnt] = x[0] / d;
            cnt++;
        }
        long up = a[0];
        long down = b[0];
        for (int i = 1; i < cnt; i++) {
            up = gcdSub(up, a[i]);
            down = gcdSub(down, b[i]);
        }
        System.out.println(up + "/" + down);
    }

    public static long gcd(long a, long b) {
        if (b == 0) return a;        
        return gcd(b, a % b);
    }

    public static long gcdSub(long a, long b) {
        if (a < b) {long temp = a; a = b; b = temp; }
        if(b==1) return a;
        return gcdSub(b,a/b);
    }
}

python

from math import *
def gcd_sub(a,b):
    if a<b: a,b = b,a
    if b==1: return a
    return gcd_sub(b,a//b);
n = int(input())
x = list(set(map(int,input().split())))  #set有去重的作用
x.sort()
n = len(x)
a=[]
b=[]
for i in range(1,n):
    d = gcd(x[i],x[0])
    a.append(x[i]//d)
    b.append(x[0]//d)
n = len(a)
up = a[0]
down = b[0]
for i in range(1,n):
    up = gcd_sub(up,a[i])
    down = gcd_sub(down,b[i])
print('%d/%d'%(up,down))

??其他练习，请到这里：洛谷的GCD题目