ABC 70 C

問題概要

• N台の時計があり、i(1 ≤ i ≤ N)番目の時計の針は、ちょうど\(T_i\)秒で時計盤を１周する。
• 全ての時計の針はまっすぐ上に向いている時、全ての時計の針がもう一度まっすぐ上に向くのに要する時間を求めよ。

制約

• 1 ≤ N ≤ 100
• 1 ≤ \(T_i\) ≤ 10¹⁸
• 答えは10¹⁸以内

考えたこと

• 明らかに時計の針のそれぞれの周回する時間の最小公倍数を求めれば良い。
• この際に、Tに関する制約が厳しいので注意する(具体的にはオーバーフローを起こさないようにする)
• C++ 14では、lcm(a,b) が未実装なので、(C++17以降なら存在する) \(|ab| = gcd(a, b) * lcm(a, b)\) の関係式を用いて求める。
• gcd(a, b) はユークリッドの互除法で求めれば良い

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

ll gcd(ll a, ll b) {
  if(b==0) return a;
  return gcd(b, a % b);
}

ll lcm(ll a, ll b) {
  ll g = gcd(a,b);
  return a / b * b;
}

int main() {
  int n; cin >> n;
  ll ans = 1LL;
  for(int i = 0; i < n; ++i) {
    int t; cin >> t;
    ans = lcm(ans, t);
  }
  
  cout << ans << endl;
  return 0;
}