Part I Preface
Part II Sketch
- 给定一个正整数 \(N(1 \leq N \leq 100)\)，表示时钟数量。
- 接下来 \(N\) 行，每行一个正整数 \(T_i(1 \leq T_i \leq 10^{18})\)，表示每个时钟旋转 \(T_i\) 秒后还会回到原来的地方。
- 求出在多少秒之后，所有时钟还会同时回到一个地方（开始时所有时钟指向同一个方向）。
Part III Analysis
不难发现，此题即求 \(N\) 个数的最小公倍数。
众所周知：\(\operatorname{lcm}(x, y) = \dfrac{x \cdot y}{\operatorname{gcd}(x,y)}\)。所以我们输入 \(N\) 个数，定义一个答案 \(ans = 1\)，从头到尾依次求 \(\operatorname{lcm}(ans, T_i)\) 即可。
Part IV Code
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int n;
LL num;
LL ans = 1;
LL gcd(LL a, LL b){
LL t;
while(b){
t = a;
a = b;
b = t % b;
}
return a;
}
LL lcm(LL a, LL b){
return a / gcd(a, b) * b;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n;
for(int i = 1; i <= n; i++){
cin >> num;
ans = lcm(ans, num);
}
cout << ans;
return 0;
}
