[AtCoder-AT_ABC070C]题解(C++)

Part I Preface

原题目(Luogu)
原题目(AtCoder)

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; 
}

Part V Record

Record