概要

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

考察

各歯車の回転数の導出

歯車 \(i\) と歯車 \(i+1\) がかみ合うとき、通過する歯の数は同じです。歯車 \(i\) が1回転すると \(T_i\) 枚の歯が進むので、歯車 \(i+1\) は \(T_i / T_{i+1}\) 回転します。

これを繰り返すと、歯車 \(1\) が \(R\) 回転したとき： - 歯車 \(2\) は \(R \cdot T_1 / T_2\) 回転 - 歯車 \(3\) は \(R \cdot T_1 / T_3\) 回転 - 一般に、歯車 \(k\) は \(R \cdot T_1 / T_k\) 回転

印が戻る条件

歯車の印が元の位置に戻るのは、その歯車の回転数がちょうど正の整数のときです。したがって、すべての \(k = 1, \ldots, N\) に対して：

\[R \cdot \frac{T_1}{T_k} \in \mathbb{Z}^{+}\]

が必要です。これは \(R\) が分数 \(T_k / T_1\) の正の整数倍であることと同値です。

分数のLCM

最小の正の \(R\) は、分数の集合 \(\{T_1/T_1, T_2/T_1, \ldots, T_N/T_1\}\) の最小公倍数 (LCM) です。

各 \(T_i / T_1\) を既約分数にします。\(g_i = \gcd(T_i, T_1)\) とすると：

\[\frac{T_i}{T_1} = \frac{T_i / g_i}{T_1 / g_i}\]

分数のLCMの公式は以下の通りです：

\[\text{lcm}\left(\frac{a_1}{b_1}, \frac{a_2}{b_2}, \ldots\right) = \frac{\text{lcm}(a_1, a_2, \ldots)}{\gcd(b_1, b_2, \ldots)}\]

具体例

\(T = [6, 4, 3]\) の場合： - \(T_1/T_1 = 1/1\), \(T_2/T_1 = 4/6 = 2/3\), \(T_3/T_1 = 3/6 = 1/2\) - 分子の集合: \(\{1, 2, 1\}\) → \(\text{lcm} = 2\) - 分母の集合: \(\{1, 3, 2\}\) → \(\gcd = 1\) - 答え: \(R = 2/1\)（歯車1が2回転すれば全印が戻る）

アルゴリズム

1. 各 \(i\) について \(g_i = \gcd(T_i, T_1)\) を計算し、分子 \(T_i/g_i\)、分母 \(T_1/g_i\) を求める
2. 全分子の LCM を計算する
3. 全分母の GCD を計算する
4. 結果を既約分数に約分して出力する

計算量

• 時間計算量: \(O(N \log(\max T_i))\)（各要素について GCD 計算と LCM 計算）
• 空間計算量: \(O(N)\)

実装のポイント

• LCM の計算では a // gcd(a, b) * b の順で計算し、オーバーフローを防ぐ（Python では多倍長整数なので問題ないが、意識すべき点）

• \(i = 1\) のとき \(T_1/T_1 = 1/1\) となり、分子 1、分母 1 が含まれるため、LCM は必ず他の分子の倍数に、GCD は必ず 1 の約数にはならない（分母に 1 が含まれるので GCD は 1 になるかと思いきや、\(T_1/g_1 = T_1/T_1 = 1\) なので分母に 1 が含まれ、全分母の GCD は必ず 1…ではなく、他の分母との GCD を取るので結果的に答えが整数にならない場合もあり得る）
  → 実際には \(i=1\) で分母が 1 になるため、\(\gcd\) に 1 が含まれ結果は必ず 1 になり…と思いがちですが、コードでは正しく全 \(i\) を処理しており、\(i=1\) で分母 1 が入るので最終的な分母の GCD は 1 になり、答えは常に整数になります。
  → 訂正: 問題文の制約上、答えが分数になる場合があります。これは「歯車 \(k\) の回転数 \(R \cdot T_1/T_k\) が整数」という条件から、\(R\) が整数とは限らないためです（\(k=1\) の条件は \(R\) が整数であることを要求しますが、実際にコードを確認すると \(i=1\) で分母 1 が含まれ GCD=1 となるため、答えの分母は 1 です）。問題の出力形式として分数を許容していますが、この導出では答えは常に整数 \(\text{lcm}(T_1/g_1, T_2/g_2, \ldots) / 1\) となります。

  ソースコード

import math
from functools import reduce

def solve():
    N = int(input())
    T = list(map(int, input().split()))
    
    # Gear 1 rotates R times. Gear i rotates R * T1 / Ti times.
    # For gear i's mark to return, R * T1 / Ti must be a positive integer.
    # So R must be a multiple of Ti / T1 for each i.
    # More precisely, R must be a multiple of Ti / gcd(Ti, T1) divided by T1 / gcd(Ti, T1).
    # Wait, let me think more carefully.
    
    # Gear 1 rotates R times. Gear k rotates R * (T1/T2) * (T2/T3) * ... * (T_{k-1}/T_k) = R * T1 / Tk times.
    # Wait, that's not right either. Let me re-derive.
    
    # Gear i and gear i+1 mesh: when gear i rotates once (Ti teeth), gear i+1 rotates Ti/T_{i+1} times.
    # So if gear 1 rotates R times, gear 2 rotates R * T1/T2 times.
    # Gear 3 rotates (R * T1/T2) * T2/T3 = R * T1/T3 times.
    # In general, gear k rotates R * T1 / Tk times.
    
    # For all marks to return: R * T1 / Tk must be a positive integer for all k = 1, ..., N.
    # For k=1: R must be a positive integer. Wait, R * T1/T1 = R must be integer.
    # For k=i: R * T1 / Ti must be integer.
    
    # So R must be a positive rational number such that:
    # R is a positive integer (from k=1)
    # R * T1 / Ti is a positive integer for all i
    
    # Wait, R being integer already comes from k=1. But R * T1 / Ti integer means
    # R must be a multiple of Ti / gcd(T1, Ti) ... let me think again.
    
    # R * T1 / Ti ∈ Z+  ⟺  R ∈ (Ti / T1) * Z+  ⟺  R = Ti * m / T1 for some positive integer m.
    # But R must satisfy this for ALL i simultaneously.
    
    # Let's write R = P/Q in lowest terms. Then P/Q * T1/Ti must be integer for all i.
    # That means T1 * P / (Ti * Q) must be integer, i.e., Ti * Q | T1 * P.
    
    # Actually, let's think of it differently.
    # R must be such that R * T1 / Ti is a positive integer for each i.
    # Equivalently, R = Ti * n_i / T1 for some positive integer n_i, for each i.
    # The minimum positive R is the LCM of the set {Ti/T1 : i=1,...,N} as fractions.
    
    # LCM of fractions: lcm(a1/b1, a2/b2, ...) = lcm(a1,a2,...) / gcd(b1,b2,...)
    # where each ai/bi is in lowest terms.
    
    # For each i, Ti/T1 in lowest terms: let g_i = gcd(Ti, T1), then numerator = Ti/g_i, denominator = T1/g_i.
    
    T1 = T[0]
    
    numerators = []
    denominators = []
    
    for i in range(N):
        Ti = T[i]
        g = math.gcd(Ti, T1)
        num = Ti // g
        den = T1 // g
        numerators.append(num)
        denominators.append(den)
    
    # LCM of all fractions = lcm(numerators) / gcd(denominators)
    
    def lcm(a, b):
        return a // math.gcd(a, b) * b
    
    result_num = reduce(lcm, numerators)
    result_den = reduce(math.gcd, denominators)
    
    # Simplify
    g = math.gcd(result_num, result_den)
    P = result_num // g
    Q = result_den // g
    
    print(f"{P}/{Q}")

solve()

---

この解説は claude4.6opus-thinking によって生成されました。