概要

\(N\) 個の歯車が一列に並んでおり、隣接する歯車同士がかみ合っている。歯車1を回したときに、すべての歯車の印が同時に元の位置に戻る最小の回転数を既約分数で求める問題。

考察

まず、歯車1を \(R\) 回転させたとき、他の歯車 \(i\) の回転数はどのように表せるかを考えます。
隣り合う歯車 \(i\) と \(i+1\) の間では、回転数の比が \(T_{i+1} : T_i\) になります。つまり、
$\( \text{歯車}i\text{の回転数} : \text{歯車}(i+1)\text{の回転数} = T_{i+1} : T_i \)$

したがって、歯車1の回転数を \(R\) とすると、歯車 \(i\) の回転数 \(R_i\) は次のように求められます： $\( R_i = R \cdot \frac{T_1}{T_2} \cdot \frac{T_2}{T_3} \cdots \frac{T_{i-1}}{T_i} = R \cdot \frac{T_1}{T_i} \)$

すべての歯車の印が元に戻るためには、各歯車の回転数 \(R_i\) が整数である必要があります。
つまり、すべての \(i\) に対して、 $\( R \cdot \frac{T_1}{T_i} \in \mathbb{Z} \quad \Leftrightarrow \quad R \cdot T_1 \equiv 0 \pmod{T_i} \)$

これは言い換えれば、「\(R \cdot T_1\) がすべての \(T_i\) の公倍数であること」が必要条件です。
特に、最小の正の \(R\) を求めたいので、
$\( R \cdot T_1 = \mathrm{lcm}(T_1, T_2, \dots, T_N) \Rightarrow R = \frac{\mathrm{lcm}(T_1, T_2, \dots, T_N)}{T_1} \)$

この値は一般に有理数になるので、最後に既約分数にする処理（分子・分母の最大公約数で割る）を行う必要があります。

素朴なアプローチでは？

例えば、愚直に各 \(R_i\) が整数になる最小の \(R\) を探そうとすると、非常に大きな数や浮動小数点誤差の問題が発生し、TLEや誤答につながります。
そのため、数学的な性質を利用して、最小公倍数と最大公約数を用いて厳密に計算する必要があります。

アルゴリズム

1. すべての歯車の歯数 \(T_1, T_2, ..., T_N\) から、それらの最小公倍数 \(L = \mathrm{lcm}(T_1, T_2, ..., T_N)\) を求める。
2. 最小の回転数 \(R\) は $\( R = \frac{L}{T_1} \)$
3. この分数を既約分数にするために、分子 \(L\) と分母 \(T_1\) の最大公約数 \(g = \gcd(L, T_1)\) で割る。
4. 結果として、\(P = L/g\), \(Q = T_1/g\) として出力する。

計算量

• 時間計算量: \(O(N + \log(\max(T_i)))\)
  各要素の \(\gcd\) や \(\mathrm{lcm}\) の計算が \(O(\log(\max(T_i)))\) で行われ、それが \(N\) 回程度繰り返される。
• 空間計算量: \(O(1)\)
  入力を除けば定数個の変数のみを使用。

実装のポイント

• Pythonの math.gcd や自前で実装した lcm 関数を使うことで、高速かつ安全に計算できる。

• 最大公約数で割って既約分数にする処理を忘れずに。

• 答えが整数の場合でも P/1 の形で出力すること。

  ソースコード

import math
from functools import reduce

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def lcm(a, b):
    return a // gcd(a, b) * b

def main():
    N = int(input())
    T = list(map(int, input().split()))
    
    # 歯車1の回転数Rと他の歯車の回転数の比を計算
    # 隣接する歯車の回転数の比は T[i+1] : T[i]
    # つまり、R1 : R2 = T[1] : T[0], R2 : R3 = T[2] : T[1], ...
    # 一般に Ri : Ri+1 = T[i] : T[i-1]
    # したがって、R1 : R2 : ... : RN = T[0] : T[1] : ... : T[N-1] の逆比
    # つまり Ri = R1 * (T[0]/T[1]) * (T[1]/T[2]) * ... * (T[i-2]/T[i-1]) 
    #          = R1 * T[0] / T[i-1]
    # しかし、これは連分数的に考えると、すべての歯車が整数回転する最小のR1は
    # 各歯車の周期（T[i]）の最小公倍数に関する条件から導かれる
    
    # 歯車1が1回転すると、歯車iは T[0]/T[1] * T[1]/T[2] * ... * T[i-1]/T[i] = T[0]/T[i] 回転
    # すべての歯車の印が元に戻るためには、各T[0]/T[i] * R が整数である必要がある
    # つまり R * T[0] / T[i] が整数 ⇔ R * T[0] ≡ 0 (mod T[i])
    # これはすべてのiについて成り立つので、
    # R * T[0] は lcm(T[1], T[2], ..., T[N-1]) の倍数である必要がある
    # 最小の正のRは lcm(T[1], T[2], ..., T[N-1]) / T[0] （ただし整数とは限らない）
    # 実際には、R = lcm(T[1], ..., T[N-1]) / T[0] は一般には有理数なので、
    # 通分して既約分数にする必要がある
    
    # より正確には、すべてのiに対して R * T[0] / T[i] が整数である最小のRを求めたい
    # これは R * T[0] がすべてのT[i]の公倍数であることを意味する
    # よって R * T[0] = lcm(T[0], T[1], ..., T[N-1])
    # R = lcm(T[0], T[1], ..., T[N-1]) / T[0]
    
    # 分子 = lcm(T[0], T[1], ..., T[N-1])
    # 分母 = T[0]
    # これを既約分数にするためにgcdで割る
    
    L = T[0]
    for i in range(1, N):
        L = lcm(L, T[i])
    
    numerator = L
    denominator = T[0]
    
    g = gcd(numerator, denominator)
    numerator //= g
    denominator //= g
    
    print(f"{numerator}/{denominator}")

if __name__ == "__main__":
    main()

この解説は qwen3-coder-480b によって生成されました。