Official
C - 歯車の同期 / Gear Synchronization Editorial
by
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\) です。
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:
