概要

すべての部屋を隙間なく敷き詰め、かつデザインの条件を満たすような正方形タイルの一辺の長さ \(d\) の最大値を求める問題です。 部屋のサイズやデザイン係数の条件を数式で整理し、最大公約数（GCD）の性質と約数列挙を利用することで、高速に解を求めることができます。

考察

条件を \(d\) に関する数式に整理していきましょう。

条件1：タイルで床を隙間なく敷き詰められる

各部屋 \(i\) について、縦 \(H_i\) と横 \(W_i\) がともに \(d\) の倍数である必要があります。 これは、「\(d\) は \(H_i\) と \(W_i\) の公約数である」と言い換えられます。すなわち、最大公約数を \(\gcd\) と表すと、 $\(d \text{ は } \gcd(H_i, W_i) \text{ の約数}\)\( がすべての \)i\( について成り立つ必要があります。 したがって、すべての部屋における縦横の最大公約数の、さらに最大公約数を \)G\( とおくと、 \)\(G = \gcd(\gcd(H_1, W_1), \gcd(H_2, W_2), \dots, \gcd(H_N, W_N))\)\( \)d\( は **\)G$ の約数** でなければなりません。

条件2：タイルの枚数が \(S_i\) の倍数である

部屋 \(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 \iff \frac{H_i W_i}{S_i} = k \cdot d^2\)\( これは、「\)d^2\( は \)\frac{H_i W_i}{S_i}\( の約数である」ことを意味します。 ここで \)m_i = \frac{H_i W_i}{S_i}\( とおくと、すべての部屋について \)d^2\( が \)m_i\( の約数である必要があります。 したがって、すべての \)m_i\( の最大公約数を \)M\( とおくと、 \)\(M = \gcd(m_1, m_2, \dots, m_N)\)\( \)d^2\( は **\)M\( の約数**（すなわち \)M\( が \)d^2$ で割り切れる）でなければなりません。

効率的な解法へのアプローチ

素朴に \(d\) を \(1\) から順に試すと、\(H_i, W_i\) が最大 \(10^9\) と非常に大きいため実行時間制限に間に合いません（TLE）。

しかし、上記の考察から \(d\) は \(G\) の約数でなければならない ことが分かっています。 \(G \le 10^9\) のとき、その約数の個数は高々 \(1344\) 個と非常に少ないです。また、\(G\) の約数は \(O(\sqrt{G})\) の時間で全列挙することができます。

したがって、以下の手順で解くことができます。 1. \(G\) の約数をすべて列挙する。 2. 約数を大きい順（降順）に並べる。 3. 大きい順に \(d\) を試し、最初に \(d^2\) が \(M\) の約数（\(M \pmod{d^2} == 0\)）となったものが求める最大の \(d\) となる。

アルゴリズム

1. 初期化: \(G = 0, M = 0\) としておきます（\(\gcd(0, x) = x\) の性質を利用するため）。
2. 各部屋の情報を処理: 各部屋 \(i\) について以下を計算し、全体の GCD を更新します。
   • \(g_i = \gcd(H_i, W_i)\) を求め、\(G = \gcd(G, g_i)\) とする。
   • \(m_i = \frac{H_i W_i}{S_i}\) を求め、\(M = \gcd(M, m_i)\) とする。
3. 約数列挙: \(G\) の約数を \(O(\sqrt{G})\) で列挙し、配列に格納します。
4. 探索: 約数の配列を大きい順にソートします。 配列の要素 \(d\) に対して、順に \(M \pmod{d^2} == 0\) であるかを判定し、最初に条件を満たした \(d\) を出力して終了します。

計算量

• 時間計算量: \(O(N \log(\min(H, W)) + \sqrt{G} + D \log D)\)

  • 各部屋の \(\gcd\) の計算に \(O(\log(\min(H, W)))\) かかります。これが \(N\) 部屋分で \(O(N \log(\min(H, W)))\) です。
  • \(G\) の約数列挙に \(O(\sqrt{G})\) かかります（最大で \(\sqrt{10^9} \approx 31622\) 回のループ）。
  • 約数の個数を \(D\) とすると、ソートに \(O(D \log D)\) かかります（\(D \le 1344\) なので一瞬です）。
  • 全体として実行時間制限に余裕で間に合います。

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

  • \(G\) の約数を格納するリストのサイズは最大で \(1344\) であり、極めて省メモリです。

実装のポイント

• 高速な入出力: \(N \le 10^5\) と入力がやや多いため、Python では sys.stdin.read().split() を用いて一括で入力を取得することで、入出力のボトルネックを防いでいます。

• 約数列挙の重複回避: \(i \times i = G\) となるような平方根のケースで、同じ約数を重複して追加しないように注意します（コード中の if i * i != G: の部分）。

  ソースコード

import sys
import math

def solve():
    # 入力を一括で読み込む
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    N = int(input_data[0])
    
    G = 0
    M = 0
    
    # 3つずつの要素を効率的に取り出す
    iterator = map(int, input_data[1:])
    for H, W, S in zip(iterator, iterator, iterator):
        g = math.gcd(H, W)
        G = math.gcd(G, g)
        
        m = (H * W) // S
        M = math.gcd(M, m)
        
    # G の約数を列挙する
    divisors = []
    limit = int(math.isqrt(G))
    for i in range(1, limit + 1):
        if G % i == 0:
            divisors.append(i)
            if i * i != G:
                divisors.append(G // i)
                
    # 約数を大きい順にソート
    divisors.sort(reverse=True)
    
    # d^2 が M を割り切る最大の d を探す
    for d in divisors:
        if M % (d * d) == 0:
            print(d)
            return

if __name__ == '__main__':
    solve()

---

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