[题解]NC14503晨跑

晨跑

https://ac.nowcoder.com/acm/problem/14503

题目

“无体育，不清华”、“每天锻炼一小时，健康工作五十年，幸福生活一辈子”

在清华，体育运动绝对是同学们生活中不可或缺的一部分。为了响应学校的号召，模范好学生王队长决定坚持晨跑。不过由于种种原因，每天都早起去跑步不太现实，所以王队长决定每a天晨跑一次。换句话说，假如王队长某天早起去跑了步，之后他会休息a-1天，然后第a天继续去晨跑，并以此类推。

王队长的好朋友小钦和小针深受王队长坚持锻炼的鼓舞，并决定自己也要坚持晨跑。为了适宜自己的情况，小钦决定每b天早起跑步一次，而小针决定每c天早起跑步一次。

某天早晨，王队长、小钦和小针在早起跑步时相遇了，他们非常激动、相互鼓励，共同完成了一次完美的晨跑。为了表述方便，我们把三位同学相遇的这天记为第0天。假设三位同学每次晨跑的时间段和路线都相同，他们想知道，下一次三人在跑步时相遇是第几天。由于三位同学都不会算，所以希望由聪明的你来告诉他们答案。

题解

此题目不难理解，三人以不同的周期跑步，求下一次共同相遇的时间。即求三个数的最小公倍数问题。

求最小公倍数，最容易想到的思路便是暴力求解，即从三个数中找出最大的一个数，从这个数开始不断递增，第一个能够被这三个数同时整除的数，即为所求最小公倍数。

暴力法题解代码（超时）

typedef long long ll;
ll solve(ll a,ll b,ll c){
    ll i = max(max(a,b),c);
    while(!(i % a == 0 && i % b == 0 && i % c == 0)){
        i++;
    }
    return i;
}

分析

这个方法思路简单，向上递增，逐个做匹配。但是该算法效率低下，由于题目输入规模可能较大1≤a,b,c≤100000，运用该算***超时。

即使将该暴力算法优化，在数据规模较大时，超时问题依然严重。

我们不得不考虑更加优秀的算法。

那么问题来了，有什么更加优秀的算法呢？

注意：已知两个数的最大公约数，只需要一步即可得到其最小公倍数。而想得到两数的最大公约数，有著名的欧几里得算法和更相减损术

所以我们可以：

使用欧几里得算法求最大公约数，再由最大公约数求出最小公倍数
使用更相减损术求最大公约数，再由最大公约数求出最小公倍数

更相减损术题解代码

#include<cstdio>
using namespace std;
typedef long long ll;
ll solve(ll a,ll b){
    ll ta = a,tb = b;
    while(a != b){
        if(a > b)
            a -= b;
        else
            b -= a;
    }
    return ta * tb / a;
}
int main(){
    ll a[3];
    scanf("%lld%lld%lld",&a[0],&a[1],&a[2]);
    printf("%lld\n",solve(solve(a[0],a[1]),a[2]));
    return 0;
}

分析

更相减损术又称辗转相减法，出自《九章算术》，是一种求最大公约数的算法。

原文：可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也。以等数约之。

译：如果一个分数能被2约分，则用2约分，否则取分数的分子和分母，用大数减小数，再取两数差和减数，反复相减，直至差与减数相等，用这个相等的数来约分。

注意：更相减损术最初是用来约分的。而两个数的最大公约数，等于第一步中约掉的若干个2的积与第二步中等数的乘积。

欧几里得算法题解代码

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;

ll solve(ll a,ll b){
    ll ta = a,tb = b;
    if(a < b)
        swap(a,b);
    while(b){
        ll t = b;
        b = a % b;
        a = t;
    }
    return ta * tb / a;
}
int main(){
    ll a[3];
    scanf("%lld%lld%lld",&a[0],&a[1],&a[2]);
    printf("%lld\n",solve(a[0],solve(a[1],a[2])));
    return 0;
}