問題概要

$N$ 台の時計があり、時計 $i$ の針はちょうど $T_{i}$ 秒で時計盤を 1 周する。

最初、全ての時計の針は真っ直ぐ上に向いており、止まっている。イルカは、全ての時計の針を同時に動かし始めた。再び、全ての時計の針が真っ直ぐ上に向くのは何秒後か？

制約

$1 \le N \le 100$
答えは $10^{18}$ 以下

考えたこと

$T_{1}, T_{2}, \dots, T_{N}$ の最小公倍数を求めればよい。そして、 $N$ 個の最小公倍数を求めるためには、次のようにすればよい。

答えを表す変数 res を用意して、res = 1 と初期化しておく
の順に
- res を、「res と T[i] の最小公倍数」で置き換える

このように求められる理由は、次の定理に基づいている。

$a_{1}, a_{2}, \dots, a_{i-1}, a_{i}$ の最小公倍数は、「 $a_{1}, a_{2}, \dots, a_{i-1}$ の最小公倍数」と $a_{i}$ の最小公倍数に一致する

つまり、前から順に最小公倍数を求めていけば良いのだ。

注意点

一般に、整数 $a, b$ の最小公倍数を求めるためには、

$\displaystyle \frac{ab}{\mathrm{gcd}(a, b)}$

を計算すればよいのだが、これを

a * b / gcd(a, b)

と実装してしまうと、a * b を計算する段階でオーバーフローしてしまうことがある。そのため、

a / gcd(a, b) * b

のように実装するとよい。

コード

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

int main() {
    long long N, T;
    cin >> N;

    long long res = 1;
    for (int i = 0; i < N; i++) {
        cin >> T;

        // res と T の最大公約数を求めて、res を置き換える
        res = res / gcd(res, T) * T;
    }
    cout << res << endl;
}