AtCoder Beginner Contest 070 C問題

AtCoder Python

C問題

難易度：茶色
時間：5分くらい

atcoder.jp


久しぶりなので、問題は簡単め。
Atcoderが4問時代の時は、茶色の問題であれど比較的難易度が簡単な気がします。

N台の時計があり、i(1≦i≦N)番目の時計の針はちょうど Ti秒で時計盤を 1周します。
最初、全ての時計の針は真っ直ぐ上に向いており、止まっています。
イルカは、全ての時計の針を同時に動かし始めました。
再び、全ての時計の針が真っ直ぐ上に向くのは何秒後でしょうか?

最小公倍数を使ってとけばいい問題です。
aとbの最小公倍数とaとbの最大公約数の積は、aとbの積となります。

その原理は単に以下の通りです。

- 最小公倍数 L
- 最大公約数 G
- 互いに素の整数 a'とb'

aとbは以下の通り。(1)
a = G・a'
b = G・b'

a'とb'は互いに素なので最小公倍数に関して以下が成り立つ。(2)
L = G・a'・b'

(1)より
a・b = (G・a')・(G・b')
a・b =  (G・a'・b')・G
a・b = G・L

最大公約数を求めるモジュールは存在するのでこれを活用します。
N個の整数の最大公倍数が一気に得られないので、O(n**2)の計算量を要しています。

import math
N = int(input())
T =  list(int(input()) for n in range(N))
ans = T[0]
 
for i in range(1,N):
  ans  = ans*T[i] // math.gcd(ans,T[i])
print(ans)