Official

C - 歯車の同期 / Gear Synchronization Editorial by sounansya


歯車 \(1\) の回転数を \(R\) としたとき、歯車 \(i\) が元の位置に戻るのは \(\displaystyle \frac{T_1}{T_i}\times R\) が整数となる時です。

\(i=1\) の場合を考えることで \(R\) は整数に限定されるので、 \(\displaystyle \frac{T_1}{T_i}\times R\) が整数となることは \(R\)\(\displaystyle \frac{T_i}{\gcd(T_1,T_i)}\) の倍数となることと同値です。したがって、求める答えは \(\displaystyle \frac{T_i}{\gcd(T_1,T_i)}\) の最小公倍数です。

答えは必ず整数となるため、分母は必ず \(1\) です。

実装例(Python3)

from math import gcd, lcm

n = int(input())
t = list(map(int, input().split()))
ans = 1
for i in range(1, n):
    ans = lcm(ans, t[i] // gcd(t[0], t[i]))
print(ans, end="/1\n")

posted:
last update: