Overview

This problem involves \(N\) gears that rotate in conjunction. The task is to find the earliest moment when all gears simultaneously reach a state of “exactly an integer number of rotations,” and output the number of rotations of gear 1 at that time as an irreducible fraction.

Analysis

1. Relationship Between “Meshing” and “Number of Teeth Advanced”

When adjacent gears mesh and rotate, if one gear advances by 1 tooth, the other also necessarily advances by 1 tooth. Therefore, when all gears rotate in conjunction, the total number of teeth advanced is the same for all gears. Let this common total number of teeth advanced be \(S\).

2. Condition for the Number of Rotations to Be an Integer

The number of teeth on each gear \(i\) is \(T_i\). When the total teeth advanced is \(S\), the number of rotations \(R_i\) of gear \(i\) is expressed as: $\(R_i = \frac{S}{T_i}\)$

For the marks on all gears to return to their original positions, the number of rotations \(R_i\) for every gear must be a positive integer. For \(R_i = \frac{S}{T_i}\) to be an integer means that the total teeth \(S\) must be a multiple of \(T_i\) (divisible by \(T_i\)).

The smallest positive integer \(S\) satisfying this for all \(i\) (\(1 \leq i \leq N\)) is the Least Common Multiple (LCM) of all \(T_i\). $\(S = \text{lcm}(T_1, T_2, \ldots, T_N)\)$

3. Deriving the Number of Rotations \(R\) of Gear 1

What we want to find is the number of rotations of gear 1 at this time: \(R = R_1 = \frac{S}{T_1}\). Since \(S\) is the least common multiple of all \(T_i\) including \(T_1\), naturally \(S\) is a multiple of \(T_1\). Therefore, \(R = \frac{S}{T_1}\) is always an integer.

When expressing the integer \(R\) in the form of an irreducible fraction \(\frac{P}{Q}\), the denominator \(Q\) is always \(1\), and the numerator \(P\) is \(R\) itself. Thus, the answer to output is always in the form P/1 (where \(P = S / T_1\)).

---

Algorithm

1. Computing the Least Common Multiple (LCM) Find the least common multiple \(S = \text{lcm}(T_1, T_2, \ldots, T_N)\) of \(N\) integers. The least common multiple of two integers \(a, b\) can be computed using the Greatest Common Divisor (GCD) as follows: $\(\text{lcm}(a, b) = \frac{a \times b}{\gcd(a, b)}\)$ Using this, we cumulatively update the LCM from left to right.

   • Initial value: \(S = T_1\)
   • For \(i = 2, 3, \ldots, N\), update \(S = \text{lcm}(S, T_i)\).

2. Outputting the Answer From the computed \(S\), calculate the number of rotations of gear 1 as \(P = S / T_1\), and output in the format P/1.

---

Complexity

• Time Complexity: \(O(N \log(\max T_i))\) We sequentially compute the GCD (Greatest Common Divisor) for \(N\) numbers. The GCD computation for two numbers can be done in \(O(\log(\max T_i))\) using the Euclidean algorithm, so the overall complexity is \(O(N \log(\max T_i))\), which is well within the time limit.

• Space Complexity: \(O(N)\) Memory space is needed to store the number of teeth \(T_i\) of the input gears in an array.

---

Implementation Notes

• Handling Arbitrary-Precision Integers From the constraints, \(T_i \leq 10^9\), and their least common multiple \(S\) can become a very large value (potentially exceeding what a 64-bit integer type can hold). In Python, arbitrary-precision integers (integers with no digit limit) are supported by default, so calculations can be performed directly without worrying about overflow. When using languages such as C++, it is necessary to use a big integer library or employ techniques such as performing appropriate prime factorization.

  Source Code

import sys
import math

def solve():
    # 入力を一括で読み込む
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    T = [int(x) for x in input_data[1:]]
    
    # すべての歯車の歯数の最小公倍数 (LCM) を求める
    curr_lcm = T[0]
    for i in range(1, N):
        g = math.gcd(curr_lcm, T[i])
        curr_lcm = (curr_lcm * T[i]) // g
        
    # 歯車1の最小回転数 R = LCM / T_1
    # R は必ず整数になるため、分母 Q は 1 となる
    P = curr_lcm // T[0]
    
    print(f"{P}/1")

if __name__ == '__main__':
    solve()

---

This editorial was generated by gemini-3.5-flash-thinking.