（数学）GCD总结

目录

简介：

算法实现：

代码：

应用：

简介：

GCD即Greatest Common Divisor.

例如，12和30的公约数有：1、2、3、6，其中6就是12和30的最大公约数。

两个整数的最大公约数主要有两种寻找方法： * 两数各分解质因子，然后取出同样有的项乘起来 * 辗转相除法（扩展版） 和最小公倍数（lcm）的关系：gcd(a, b)×lcm(a, b) = ab 两个整数的最大公因子可用于计算两数的最小公倍数，或分数化简成最简分数。 两个整数的最大公因子和最小公倍数中存在分配律： * gcd(a, lcm(b, c)) = lcm(gcd(a, b), gcd(a, c)) * lcm(a, gcd(b, c)) =gcd(lcm(a, b), lcm(a, c)) 在坐标里，将点(0, 0)和(a, b)连起来，通过整数坐标的点的数目（除了(0, 0)一点之外）就是gcd(a, b)。

gcd递归定理及证明

gcd递归定理是指gcd(a,b)=gcd(b,a%b),其中%表示取余数。

证明如下：

我们只需证明gcd(a,b)和gcd(b,a%b)可以互相整除即可。

对于gcd(a,b)，它是a和b的线性组合中的最小正元素，gcd(b,a%b) 是b与a%b的一个线性组合，而a%b是a与b的一个线性组合，因而gcd(b,a%b)是一个a与b的线性组合，因为a,b都能被gcd(a,b)整除，因而任何一个a与b的线性组合都能被gcd(a,b)整除，所以gcd(b,a%b)能被gcd(a,b)整除。

反之亦然。

算法实现：

如果感觉上面的方法有点不理解的话，请看下面的证明：

代码：

递归版本：

int gcd(int a,int b)//求a，b最大公约数
{
    if(b==0)
        return a;
    return gcd(b,a%b);
}

非递归版本：

int  gcd(int a,int b)
{
    if(!a)
        return b;
    int c;
    while(b)
    {
        c=b;
        b=a%b;
        a=c;
    }
    return a;
}

应用：

一、题目描述

    在一个由1×1的格子组成的平面上，给出两个格子的交点P1(x1,y1)和P2(x2,y2).要求计算出线段P1P2上还有多少格子交点。

二、样例

    输入：P1=(1,11),P2=(5,3)

    输出：3{(2,9),(3,7),(4,5)}

题意：

给定坐标平面上的两个顶点，问连接两点所得到的线段与坐标轴交点相交的个数。

题解：

通过两点p1和p2求得它们的向量坐标，既然是要求交点的个数，那么就算是我们使用线段与y=x或y=-x对称的线段也是能够求出答案的（保证辗转相除的两项都大于0），我们求出这两个数的最大公因数，用横纵坐标除以这个数得到的横纵坐标是两个互质的数，我们可以以这两个数作为基底，同时让横纵坐标乘以一个数k，不难想出这个k的取值范围是1到最大公因数。

所以经过推导，答案就是最大公因数减去一。

代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<math.h>
using namespace std;
typedef  long long LL;

int gcd(int a,int b)
{
    if(a<b)
    {
        int c=a;
        a=b;
        b=c;
    }
    if(b==0)
        return a;
    return gcd(b,a%b);
}

int main()
{
    int x1,y1,x2,y2;
    cin>>x1>>y1>>x2>>y2;
    int b1=abs(y2-y1);
    int a1=abs(x2-x1);//求出向量坐标
    int c=gcd(a1,b1);//最大公因数
    printf("%d\n",c-1);
    return 0;
}