GCD(最大公约数)

定义

　　gcd,最大公因数（英语：highest common factor，hcf）也称最大公约数（英语：greatest common divisor，gcd）是数学词汇，指能够整除多个整数的最大正整数。而多个整数不能都为零。

c/c++语言实现求GCD

　　求两个整数最大公约数主要的方法有：

  • 穷举法
  • 素因数分解
  • 短除法
  • 辗转相除法
    　　这里我们主要用辗转相除法(又称欧几里得算法)求最大公因数。
    辗转相除法：用较大数除以较小数，再用出现的余数（第一余数）去除除数，再用出现的余数（第二余数）去除第一余数，如此反复，直到最后余数是0为止。如果是求两个数的最大公约数，那么最后的除数就是这两个数的最大公约数。
    具体代码实现
int gcd(int x,int y)
{
    if(y==0)
        return x;
    else
        return gcd(y,x%y);
}

//这种方法可以用到三目运算符来简化代码

int gcd(int x.int y)
{
    return y==0?x:gcd(y,x%y);
}

上面这种写法用到了递归，还有就是不用递归的写法

int gcd(int x,int y)
{
    int z;
    while(y!=0)
    {
        z=x%y;
        x=y;
        y=z;
    }
    return x;
}

上面两种写法本质上是一样的，就是辗转相除法.

实例分析

HDUOJ 2504

题目描述
又见GCD
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

有三个正整数a,b,c(a,b,c是三个大于0小于1e6的数)，其中c不等于b。若a和c的最大公约数为b，现已知a和b，求满足条件的最小的c。

Input
第一行输入一个n，表示有n组测试数据，接下来的n行，每行输入两个正整数a,b。

Output
输出对应的c，每组测试数据占一行。

Sample Input
2
6 2
12 4
Sample Output
4
8
题目分析
这是一道简单的考察最大公约数的问题。给定两个数a,b求满足gcd(a,c)=b的最小的c的值且c不等于b。数据范围在1e6以内，并且c是b的倍数，所以可以每次给b加c，每次判断是不是答案即可。即

c=2*b;    //因为b是a,c的最大公约数，所以c肯定是大于等于b的。又因为题目中了b不等于c，所以给c定初值为2*b。
while(gcd(a,c)!=b)
    b+=c;    //c是b的倍数，所以可以每次给b加c

完整代码实现

#include<stdio.h>
int gcd(int x,int y)
{
    if(y==0) return x;
    return gcd(y,x%y);
}
int main()
{
    int a,b,n;
    scanf("%d",&n);
    while(n--)
    {
        scanf("%d %d",&a,&b);
        int c=2*b;
        while(gcd(a,c)!=b)
        c+=b;
        printf("%d\n",c);
    }
    return 0;
}

在vj上提交运行的结果

LCM(最小公倍数)

定义

LCM,两个或多个整数公有的倍数叫做它们的公倍数，其中除0以外最小的一个公倍数就叫做这几个整数的最小公倍数。

c/c++实现求LCM

n个数的最小公倍数就等于这n个数乘积的绝对值除以这n个数的最大公约数。即lcm(a,b)=a*b/gcd(a,b)。换句话说就是，如果n个数以及这n个数的最大公约数已知，就能求出这n个数的最小公倍数。
具体代码实现

int gcd(int x,int y)
{
    return y==0?x:gcd(y,x%y);
}
int lcm(int x,int y)
{
    return x*y/gcd(x,y);
}

实例分析

蓝桥杯历届试题 核桃的数量

题目描述
历届试题 核桃的数量
时间限制：1.0s 内存限制：256.0MB

问题描述
小张是软件项目经理，他带领3个开发组。工期紧，今天都在加班呢。为鼓舞士气，小张打算给每个组发一袋核桃（据传言能补脑）。他的要求是：

  1. 各组的核桃数量必须相同
  2. 各组内必须能平分核桃（当然是不能打碎的）
  3. 尽量提供满足1,2条件的最小数量（节约闹革命嘛）

输入格式
输入包含三个正整数a, b, c，表示每个组正在加班的人数，用空格分开（a,b,c是三个小于30的数）
输出格式
输出一个正整数，表示每袋核桃的数量。
样例输入1
2 4 5
样例输出1
20
样例输入2
3 1 1
样例输出2
3
题目分析 经过看题的过程可以发现这只是一个让求三个数的最小公倍数的水题，直接写就行。
具体代码实现

#include<stdio.h>
int gcd(int x,int y)
{
    return y==0?x:gcd(y,x%y);
}
int lcm(int x,int y)
{
    return x*y/gcd(x,y);
}
int main()
{
    int a,b,c;
    scanf("%d %d %d",&a,&b,&c);
    printf("%d\n",lcm(lcm(a,b),c));
    return 0;
}

在蓝桥评测系统上提交运行的结果

总结

关于最大公约数以及最小公倍数的东西先总结到这里，以后再有拓展的话会继续添加。

赏