题解 P4057 【[Code+#1]晨跑】

· · 题解

这题是一道很简单的最小公倍数问题，那么就来普及一下关于最小公倍数的知识点吧。（神犇勿喷，鉴于是写题解，所以就写得细一点）

首先，了解一下最大公约数——GCD。

1：辗转相除法

辗转相除法， 又名 欧几里德算法（Euclidean algorithm）

设两数为a、b(a>b)，用gcd(a,b)表示a，b的 最大公约数，r=a (mod b) 为a除以b的余数，k为a除以b的商，即a÷b=k .......r。辗转相除法即是要证明gcd(a,b)=gcd(b,r)。

第一步：令c=gcd(a,b)，则设a=mc，b=nc

第二步：根据前提可知r =a-kb=mc-knc=(m-kn)c

第三步：根据第二步结果可知c也是r的因数

第四步：可以断定m-kn与n 互质(假设m-kn=xd，n=yd (d>1)，则m=kn+xd=kyd+xd=(ky+x)d，则a=mc=(ky+x)cd，b=nc=ycd，则a与b的一个公约数cd>c，故c非a与b的最大公约数，与前面结论矛盾)，因此c也是b与r的最大公约数。

从而可知gcd(b,r)=c，继而gcd(a,b)=gcd(b,r)。

其次，了解一下最小公倍数（LCM）

假设：a=10,b=15,求他们的最小公倍数。

先质数分解：

a=25,b=35;

求他们的最小公倍数，若他们互质，则ans=a*b;

但是a,b有共同的因子（最大公约数）,所以：

ans=a*b/(gcd(a,b));

现在上代码：

首先：GCD——辗转相除：

long long gcd(long long x,long long y){

    if (x%y==0){
        return y;
    }
    return gcd(y,x%y)；
}

其次，最小公倍数——LCM：

long long lcm(long long x,long long y){
    return x*y/gcd(x,y);
}

注：数据原因，用long long。

原本的最小公倍数是两个数，但是，此题是三个数，也没关系，先求a,b的LCM，记为x，再求x和c的LCM，然后就结束了，输出答案。

完整代码：

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;//头文件

long long a,b,c;//三个晨跑的人（周期）

long long gcd(long long x,long long y){//辗转相除求最大公约数
    if (x%y==0){
        return y;
    }
    return gcd(y,x%y);//重点
}

long long lcm(long long x,long long y){//最小公倍数（用GCD求）
    return x*y/gcd(x,y);
} 

int main()
{
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    scanf ("%lld%lld%lld",&a,&b,&c);//读入
    long long ans=0;
    ans=lcm(a,lcm(b,c));//直接求答案
    cout<<ans<<endl;//输出
    return 0;
}