Overview

\(N\) gears are arranged in a row, with adjacent gears meshing with each other. The problem asks to find, as an irreducible fraction, the minimum number of rotations of gear 1 such that the marks on all gears simultaneously return to their original positions.

Analysis

First, let’s consider how the number of rotations of each gear \(i\) can be expressed when gear 1 is rotated \(R\) times.
Between adjacent gears \(i\) and \(i+1\), the ratio of rotations is \(T_{i+1} : T_i\). That is,
$\( \text{Rotations of gear }i : \text{Rotations of gear }(i+1) = T_{i+1} : T_i \)$

Therefore, if the number of rotations of gear 1 is \(R\), the number of rotations \(R_i\) of gear \(i\) can be expressed as: $\( 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} \)$

For the marks on all gears to return to their original positions, the number of rotations \(R_i\) of each gear must be an integer.
In other words, for all \(i\), $\( R \cdot \frac{T_1}{T_i} \in \mathbb{Z} \quad \Leftrightarrow \quad R \cdot T_1 \equiv 0 \pmod{T_i} \)$

This means that “\(R \cdot T_1\) must be a common multiple of all \(T_i\)” is a necessary condition.
In particular, since we want to find the smallest positive \(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} \)$

This value is generally a rational number, so we need to reduce it to an irreducible fraction (divide both numerator and denominator by their greatest common divisor).

What about a naive approach?

For example, if you try to naively search for the smallest \(R\) such that each \(R_i\) is an integer, you will encounter problems with very large numbers or floating-point errors, leading to TLE or wrong answers.
Therefore, it is necessary to compute exactly using mathematical properties, specifically the least common multiple and greatest common divisor.

Algorithm

1. From the number of teeth \(T_1, T_2, ..., T_N\) of all gears, compute their least common multiple \(L = \mathrm{lcm}(T_1, T_2, ..., T_N)\).
2. The minimum number of rotations \(R\) is $\( R = \frac{L}{T_1} \)$
3. To reduce this fraction to lowest terms, divide by the greatest common divisor \(g = \gcd(L, T_1)\) of the numerator \(L\) and denominator \(T_1\).
4. Output the result as \(P = L/g\), \(Q = T_1/g\).

Complexity

• Time complexity: \(O(N + \log(\max(T_i)))\)
  The computation of \(\gcd\) and \(\mathrm{lcm}\) for each element takes \(O(\log(\max(T_i)))\), and this is repeated about \(N\) times.
• Space complexity: \(O(1)\)
  Only a constant number of variables are used aside from the input.

Implementation Notes

• By using Python’s math.gcd or a self-implemented lcm function, you can compute efficiently and safely.

• Don’t forget to reduce to an irreducible fraction by dividing by the greatest common divisor.

• Even when the answer is an integer, output it in the form P/1.

  Source Code

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()

This editorial was generated by qwen3-coder-480b.