Overview

This problem asks us to find the minimum positive number of rotations \(R\) of gear \(1\) such that all \(N\) gears meshed in a line simultaneously have “a positive integer number of rotations” (= their marks return to their original positions). The answer should be expressed as an irreducible fraction.

Analysis

1. Relationship Between Gear Rotations

When gear \(1\) rotates \(R\) times, the total number of teeth advanced is \(R \times T_1\). Since adjacent gears are meshed together, the total number of teeth advanced is equal for all gears. Therefore, if we denote the number of rotations of gear \(i\) as \(R_i\), the following equality holds: $\(R_i \times T_i = R \times T_1\)\( From this, the number of rotations \)R_i\( of gear \)i\( can be expressed as: \)\(R_i = R \frac{T_1}{T_i}\)$

2. Condition for Marks to Return to Original Positions

For the marks on all gears to simultaneously return to their original positions, the number of rotations \(R_i\) must be a positive integer for all \(i\) (\(1 \leq i \leq N\)). That is, using some positive integer \(k_i\), it must be expressible as: $\(R \frac{T_1}{T_i} = k_i \implies R = k_i \frac{T_i}{T_1}\)\( This means that the number of rotations \)R\( of gear \)1\( must be an integer multiple of \)\frac{T_i}{T_1}\( for all \)i$.

Therefore, the minimum \(R\) we seek is the Least Common Multiple (LCM) of the set of rational numbers \(\left\{ \frac{T_1}{T_1}, \frac{T_2}{T_1}, \dots, \frac{T_N}{T_1} \right\}\).

3. How to Compute the LCM of Fractions

In general, the LCM of multiple irreducible fractions \(\frac{a_i}{b_i}\) (\(\gcd(a_i, b_i) = 1\)) can be computed using the following formula: $\(\text{lcm}\left(\frac{a_1}{b_1}, \frac{a_2}{b_2}, \dots, \frac{a_N}{b_N}\right) = \frac{\text{lcm}(a_1, a_2, \dots, a_N)}{\text{gcd}(b_1, b_2, \dots, b_N)}\)$

To apply this formula, we convert \(\frac{T_i}{T_1}\) to an irreducible fraction \(\frac{a_i}{b_i}\) for each \(i\). Letting \(g_i = \gcd(T_i, T_1)\), we get: $\(a_i = \frac{T_i}{g_i}, \quad b_i = \frac{T_1}{g_i}\)$ and these are coprime (forming an irreducible fraction).

From this, the numerator \(P\) and denominator \(Q\) of the answer can be computed as follows: - \(P = \text{lcm}(a_1, a_2, \dots, a_N)\) - \(Q = \text{gcd}(b_1, b_2, \dots, b_N)\)

Finally, by dividing the computed \(P\) and \(Q\) by their greatest common divisor, we obtain the final irreducible fraction \(\frac{P}{Q}\).

Algorithm

1. Initialize \(P = 1, Q = 0\) (the initial value of \(Q\) is set to \(0\) or \(b_1\) so that \(b_1\) is directly assigned in the first step).
2. For each \(i = 0, 1, \dots, N-1\), repeat the following:
   • Compute \(g = \gcd(T_i, T_1)\).
   • Compute \(a_i = T_i / g\) and \(b_i = T_1 / g\).
   • Update \(P = \text{lcm}(P, a_i)\).
   • Update \(Q = \gcd(Q, b_i)\) (for \(i=0\), set \(Q = b_0\)).
3. Finally, compute \(g_{pq} = \gcd(P, Q)\), and set \(P = P / g_{pq}\), \(Q = Q / g_{pq}\) to make it an irreducible fraction.
4. Output \(P\) and \(Q\) separated by /.

Complexity

• Time Complexity: \(O(N \log(\max T_i))\) For each gear, we compute the greatest common divisor (\(\gcd\)) and least common multiple (\(\text{lcm}\)) using the Euclidean algorithm. Each computation takes \(O(\log(\max T_i))\), and since this is repeated \(N\) times, the overall time complexity is sufficiently fast to fit within the time limit.

• Space Complexity: \(O(N)\) Memory space is required to store the input array \(T\).

Implementation Notes

• Overflow Prevention According to the constraints, the final answer’s \(P, Q\) are guaranteed to be at most \(10^{18}\) (within the range of the 64-bit integer type long long). However, during intermediate computations (especially when computing \(P = \text{lcm}(P, a_i)\)), values may temporarily exceed \(10^{18}\). Therefore, by using __int128_t, a 128-bit integer type available in C++ environments, we can safely prevent overflow.

• Input/Output of __int128_t Since __int128_t cannot be directly output using standard std::cout, we implement a custom function (print128) that converts the number to a decimal string for output.

  Source Code

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <string>

using namespace std;

using int128 = __int128_t;

int128 gcd128(int128 a, int128 b) {
    while (b) {
        a %= b;
        swap(a, b);
    }
    return a;
}

int128 lcm128(int128 a, int128 b) {
    if (a == 0 || b == 0) return 0;
    return (a / gcd128(a, b)) * b;
}

void print128(int128 x) {
    if (x == 0) {
        cout << 0;
        return;
    }
    string s = "";
    while (x > 0) {
        s += (char)('0' + (x % 10));
        x /= 10;
    }
    reverse(s.begin(), s.end());
    cout << s;
}

int main() {
    // Optimize standard I/O operations for speed
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    if (!(cin >> N)) return 0;

    vector<long long> T(N);
    for (int i = 0; i < N; ++i) {
        cin >> T[i];
    }

    int128 P = 1;
    int128 Q = 0;

    for (int i = 0; i < N; ++i) {
        int128 t = T[i];
        int128 t1 = T[0];
        int128 g = gcd128(t, t1);
        int128 a = t / g;
        int128 b = t1 / g;

        P = lcm128(P, a);
        if (i == 0) {
            Q = b;
        } else {
            Q = gcd128(Q, b);
        }
    }

    // Ensure the fraction is irreducible (mathematically it already is, but for safety)
    int128 g_pq = gcd128(P, Q);
    P /= g_pq;
    Q /= g_pq;

    print128(P);
    cout << "/";
    print128(Q);
    cout << "\n";

    return 0;
}

---

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