概要

本問題は、一列にかみ合って連動する \(N\) 個の歯車において、すべての歯車が同時に「回転数が正の整数」となる（＝印が元の位置に戻る）ような、歯車 \(1\) の最小の正の回転数 \(R\) を既約分数で求める問題です。

考察

1. 歯車の回転数の関係式

歯車 \(1\) が \(R\) 回転したとき、進む歯の総数は \(R \times T_1\) です。隣り合う歯車はかみ合っているため、すべての歯車で進む歯の総数は等しくなります。 したがって、歯車 \(i\) の回転数を \(R_i\) とすると、以下の等式が成り立ちます。 $\(R_i \times T_i = R \times T_1\)\( これより、歯車 \)i\( の回転数 \)R_i\( は次のように表せます。 \)\(R_i = R \frac{T_1}{T_i}\)$

2. 印が元の位置に戻る条件

すべての歯車の印が同時に元の位置に戻るためには、すべての \(i\) （\(1 \leq i \leq N\)）について、回転数 \(R_i\) が正の整数でなければなりません。 すなわち、ある正の整数 \(k_i\) を用いて、 $\(R \frac{T_1}{T_i} = k_i \implies R = k_i \frac{T_i}{T_1}\)\( と表せる必要があります。これは、歯車 \)1\( の回転数 \)R\( が、すべての \)i\( について \)\frac{T_i}{T_1}$ の整数倍でなければならないことを意味します。

したがって、求める最小の \(R\) は、有理数の集合 \(\left\{ \frac{T_1}{T_1}, \frac{T_2}{T_1}, \dots, \frac{T_N}{T_1} \right\}\) の最小公倍数（LCM）となります。

3. 分数の最小公倍数の求め方

一般に、複数の既約分数 \(\frac{a_i}{b_i}\)（\(\gcd(a_i, b_i) = 1\)）の最小公倍数は、以下の公式で求めることができます。 $\(\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)}\)$

この公式を適用するために、各 \(i\) について \(\frac{T_i}{T_1}\) を既約分数 \(\frac{a_i}{b_i}\) に変換します。 \(g_i = \gcd(T_i, T_1)\) とすると、 $\(a_i = \frac{T_i}{g_i}, \quad b_i = \frac{T_1}{g_i}\)$ と表せ、これらは互いに素（既約分数）になります。

これより、求める答の分子 \(P\) と分母 \(Q\) は以下のように計算できます。 - \(P = \text{lcm}(a_1, a_2, \dots, a_N)\) - \(Q = \text{gcd}(b_1, b_2, \dots, b_N)\)

最後に、求めた \(P\) と \(Q\) をさらにそれらの最大公約数で割ることで、最終的な既約分数 \(\frac{P}{Q}\) を得ることができます。

アルゴリズム

1. \(P = 1, Q = 0\) で初期化します（\(Q\) の初期値は、最初のステップで \(b_1\) をそのまま代入するために \(0\) または \(b_1\) とします）。
2. 各 \(i = 0, 1, \dots, N-1\) について以下を繰り返します。
   • \(g = \gcd(T_i, T_1)\) を計算する。
   • \(a_i = T_i / g\)、\(b_i = T_1 / g\) を計算する。
   • \(P = \text{lcm}(P, a_i)\) に更新する。
   • \(Q = \gcd(Q, b_i)\) に更新する（ただし \(i=0\) のときは \(Q = b_0\) とする）。
3. 最後に \(g_{pq} = \gcd(P, Q)\) を計算し、\(P = P / g_{pq}\)、\(Q = Q / g_{pq}\) とすることで既約分数にします。
4. \(P\) と \(Q\) を / で区切って出力します。

計算量

• 時間計算量: \(O(N \log(\max T_i))\) 各歯車において、最大公約数（\(\gcd\)）および最小公倍数（\(\text{lcm}\)）の計算をユークリッドの互除法を用いて行います。1回あたりの計算量は \(O(\log(\max T_i))\) であり、これを \(N\) 回繰り返すため、全体の時間計算量は十分に高速で実行時間制限に間に合います。

• 空間計算量: \(O(N)\) 入力された配列 \(T\) を保持するためのメモリ空間が必要です。

実装のポイント

• オーバーフローへの対策 制約より、最終的な答えの \(P, Q\) は \(10^{18}\) 以下（64ビット整数型 long long に収まる範囲）であることが保証されています。しかし、計算の途中過程（特に \(P = \text{lcm}(P, a_i)\) の計算時）において、一時的に \(10^{18}\) を超える値が発生する可能性があります。 そのため、C++環境で利用可能な128ビット整数型である __int128_t を使用して計算を行うことで、オーバーフローを安全に防ぐことができます。

• __int128_t の入出力 __int128_t は標準の std::cout で直接出力することができないため、数値を10進数の文字列に変換して出力するカスタム関数（print128）を実装しています。

  ソースコード

#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;
}

---

この解説は gemini-3.5-flash-thinking によって生成されました。