P4057 [Code+#1] 晨跑——题解

解题思路

同时晨跑的天数必须同时是 $a,b,c$ 的倍数，最早的正天数就是三者最小公倍数。先求两个数的最小公倍数，再与第三个数求最小公倍数。使用 a/gcd(a,b)*b 降低中间乘积溢出风险。

复杂度分析

求最大公约数的时间复杂度为 $O(\log V)$，空间 $O(1)$。

C++17 参考代码

#include <bits/stdc++.h>
using namespace std;
long long lcm2(long long a,long long b){return a/gcd(a,b)*b;}
int main(){long long a,b,c;cin>>a>>b>>c;cout<<lcm2(lcm2(a,b),c)<<'\n';return 0;}

#include <bits/stdc++.h> using namespace std; long long lcm2(long long a,long long b){return a/gcd(a,b)*b;} int main(){long long a,b,c;cin>>a>>b>>c;cout<<lcm2(lcm2(a,b),c)<<'\n';return 0;}