概要

この問題は、与えられた \(N\) 個の部屋すべてについて、部屋の寸法 \(H_i, W_i\) およびデザイン係数 \(S_i\) から決まる条件を満たす、正方形タイルの一辺の長さ \(d\) の最大値を求める問題です。

数式を適切に整理することで、求める \(d\) が満たすべき条件を「最大公約数（GCD）の約数」の形に落とし込むことができ、効率的に解くことができます。

考察

条件を一つずつ整理していきましょう。

条件1：すべての部屋を隙間なく敷き詰められる

一辺の長さ \(d\) のタイルで部屋 \(i\) を隙間なく敷き詰めるためには、部屋の縦と横の長さがともに \(d\) の倍数である必要があります。 すなわち、すべての \(i\) について以下が成り立ちます。 - \(d\) は \(H_i\) の約数である - \(d\) は \(W_i\) の約数である

これは、「\(d\) は \(H_i\) と \(W_i\) の公約数である」と言い換えられます。\(H_i\) と \(W_i\) の最大公約数を \(g_i = \gcd(H_i, W_i)\) とおくと、 \(d\) は \(g_i\) の約数でなければなりません。

これがすべての部屋 \(i\) について成り立つ必要があるため、\(d\) はすべての \(g_i\) の公約数、すなわち \(G = \gcd(g_1, g_2, \dots, g_N)\) の約数でなければなりません。

条件2：タイルの枚数がデザイン係数の倍数である

部屋 \(i\) に使うタイルの枚数は \(C_i = \frac{H_i}{d} \times \frac{W_i}{d} = \frac{H_i W_i}{d^2}\) 枚です。これが \(S_i\) の倍数である必要があります。 数式で表すと、ある整数 \(k\) を用いて以下のように書けます。

\[ \frac{H_i W_i}{d^2} = k \cdot S_i \]

この式を \(d^2\) について整理すると、次のようになります。

\[ \frac{H_i W_i}{S_i} = k \cdot d^2 \]

問題の制約より \(H_i W_i\) は \(S_i\) の倍数であるため、 \(A_i = \frac{H_i W_i}{S_i}\) は常に整数です。 したがって、上の式は「\(d^2\) は \(A_i\) の約数である」ということを意味します。

これがすべての部屋 \(i\) について成り立つ必要があるため、\(d^2\) はすべての \(A_i\) の公約数、すなわち \(M = \gcd(A_1, A_2, \dots, A_N)\) の約数でなければなりません。

まとめ

求める最大の正の整数 \(d\) は、以下の2つの条件を同時に満たすもののうち最大値です。 1. \(d\) は \(G\) の約数である 2. \(d^2\) は \(M\) の約数である（すなわち、 \(M \pmod{d^2} == 0\)）

\(G\) の最大値は \(\min(H_i, W_i) \le 10^9\) であるため、\(G\) の約数は \(O(\sqrt{G})\) で全列挙できます。列挙した約数を大きい順に調べ、条件2を満たす最初の \(d\) が答えとなります。

アルゴリズム

1. 最大公約数の計算: 各部屋 \(i\) について、以下を計算しながら全体の最大公約数 \(G\) と \(M\) を更新します。

   • \(g_i = \gcd(H_i, W_i)\)
   • \(A_i = \frac{H_i W_i}{S_i}\)
   • \(G = \gcd(G, g_i)\)
   • \(M = \gcd(M, A_i)\)

2. \(G\) の約数列挙: \(1\) から \(\sqrt{G}\) までの整数で \(G\) を割り切るものを探し、 \(G\) の約数をすべて列挙します。

3. 探索: 列挙した約数を降順（大きい順）にソートします。 先頭から順に \(d\) を取り出し、 \(M\) が \(d^2\) で割り切れる（M % (d * d) == 0）か判定します。最初に条件を満たした \(d\) が求める最大値です。

計算量

• 時間計算量: \(O(N \log(\max(H_i, W_i)) + \sqrt{G} + K \log K)\)

  • \(N\) 個の入力に対する \(\gcd\) の計算に \(O(N \log(\max(H_i, W_i)))\) かかります。
  • \(G\) の約数列挙に \(O(\sqrt{G})\) かかります。 \(G \le 10^9\) より、 \(\sqrt{G} \le 31622\) 回のループで済みます。
  • \(G \le 10^9\) のとき、約数の個数 \(K\) は最大でも \(1344\) 個です。そのため、約数のソートにかかる \(O(K \log K)\) や、条件を満たすかどうかの判定にかかる \(O(K)\) は十分に高速です。
  • 全体として実行時間制限に余裕で間に合います。

• 空間計算量: \(O(K)\)

  • \(G\) の約数を格納する配列のサイズ \(K\)（最大 \(1344\)）に依存するため、メモリ使用量は極めてわずかです。

実装のポイント

• オーバーフローへの注意: \(H_i \times W_i\) は最大で \(10^9 \times 10^9 = 10^{18}\) となり、標準的な 64 ビット符号付き整数（long long）の最大値（約 \(9 \times 10^{18}\)）に収まりますが、乗算を行う過程でオーバーフローする危険を避けるため、一時的に unsigned __int128（128ビット整数）を使用して計算を行っています。 同様に、約数 \(d\) に対する \(d^2\) の計算も最大で \(10^{18}\) に達するため、判定の際にも unsigned __int128 を使用することで安全に余りを計算できます。

  ソースコード

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

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

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

    long long G = 0;
    long long M = 0;

    for (int i = 0; i < N; ++i) {
        long long H, W, S;
        cin >> H >> W >> S;
        long long g = std::gcd(H, W);
        if (G == 0) {
            G = g;
        } else {
            G = std::gcd(G, g);
        }

        unsigned __int128 HW = (unsigned __int128)H * W;
        long long A = HW / S;

        if (M == 0) {
            M = A;
        } else {
            M = std::gcd(M, A);
        }
    }

    vector<long long> divisors;
    for (long long i = 1; i * i <= G; ++i) {
        if (G % i == 0) {
            divisors.push_back(i);
            if (i * i != G) {
                divisors.push_back(G / i);
            }
        }
    }

    sort(divisors.rbegin(), divisors.rend());

    long long ans = 1;
    for (long long d : divisors) {
        unsigned __int128 d2 = (unsigned __int128)d * d;
        if (M % d2 == 0) {
            ans = d;
            break;
        }
    }

    cout << ans << "\n";

    return 0;
}

---

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