概要

すべての部屋を同じ正方形タイル（辺長 \(d\)）で敷き詰め、さらに「各部屋で使うタイル枚数が \(S_i\) の倍数」という条件も満たすような、最大の \(d\) を求めます。

考察

1) まず「敷き詰め可能」条件から \(d\) の候補は絞れる

部屋 \(i\) を辺長 \(d\) の正方形で敷き詰めるには、\(H_i, W_i\) がともに \(d\) の倍数である必要があります。
つまり \(d\) は全ての \(H_i, W_i\) を割り切る必要があるので、 [ d \mid \gcd(H_1,W_1,H_2,W_2,\dots,H_N,W_N) ] が成り立ちます。ここで [ g=\gcd(\text{全 }H_i\text{ と全 }W_i) ] とおけば、\(d\) の候補は「\(g\) の約数」に限られます。

素朴に \(g\) の全約数を列挙して大きい順にチェックする方法も考えられますが、\(g\) の約数個数は最悪でかなり多く、さらに各約数に対して \(N(=10^5)\) 部屋を確認すると重くなりがちです。

2) 「タイル枚数が \(S_i\) の倍数」を素因数ごとに見る

部屋 \(i\) で使うタイル枚数は [ C_i=\frac{H_i}{d}\cdot\frac{W_i}{d}=\frac{H_iW_i}{d^2} ] で、条件は [ S_i \mid C_i \quad\Longleftrightarrow\quad S_i \mid \frac{H_iW_i}{d^2} ] です。

ここで素数 \(p\) ごとの指数（\(p\) で何回割れるか）を使うと整理できます。\(v_p(x)\) を「\(x\) に含まれる素数 \(p\) の指数」とすると、 [ v_p(C_i)=v_p(H_i)+v_p(W_i)-2v_p(d) ] なので、 [ S_i \mid C_i \quad\Longleftrightarrow\quad v_p(H_i)+v_p(W_i)-2v_p(d)\ \ge\ v_p(S_i) ] すなわち [ 2v_p(d)\ \le\ v_p(H_i)+v_p(W_i)-v_p(S_i) ] [ v_p(d)\ \le\ \left\lfloor\frac{v_p(H_i)+v_p(W_i)-v_p(S_i)}{2}\right\rfloor ] となります。

つまり、各素数 \(p\) について「\(d\) に含められる \(p\) の指数の上限」が各部屋から計算でき、その最小値を取ればよいことが分かります。

3) 調べる素数は \(g\) を割る素数だけでよい

そもそも \(d \mid g\) なので、\(d\) に現れうる素数は \(g\) の素因数だけです。
よって、\(g\) を素因数分解し、その素数それぞれについて許される指数を求めれば答えが作れます。

アルゴリズム

1. 全ての \(H_i, W_i\) の最大公約数 [ g=\gcd(H_1,W_1,H_2,W_2,\dots,H_N,W_N) ] を計算する。
   もし \(g=1\) なら、取り得る \(d\) は \(1\) しかないので答えは \(1\)。

2. \(g\) を素因数分解し、\(g=\prod p^{e_0}\) の形にする。

3. 各素数 \(p\) について、\(d\) に入れられる指数 \(e\) を次で決める：

   • まず \(e=e_0\)（\(d\mid g\) より、これ以上は入れられない）
   • 各部屋 \(i\) について [ a=v_p(H_i),\quad b=v_p(W_i),\quad c=v_p(S_i) ] [ t=\left\lfloor\frac{a+b-c}{2}\right\rfloor ] とおき、\(e=\min(e,t)\) に更新する。
   • 最終的な \(e\) が、その素数 \(p\) の指数。

4. 答えは [ d=\prod p^{e} ] として求まる。

※制約より「\(H_iW_i\) は \(S_i\) の倍数」なので、\(d=1\) は必ず可能で、上の計算でも各 \(t\) が負になりにくい（少なくとも全体として解が存在）ことが保証されています。

計算量

• 時間計算量:
  
  • \(g\) の計算が \(O(N\log \max(H_i,W_i))\) 程度
    
  • \(g\) の素因数分解が \(O(\sqrt{g})\)
    
  • 素因数の個数を \(k\) とすると、各部屋で \(v_p\) を数えるので \(O(N\cdot k\cdot \log \max(H_i,W_i))\) 程度（\(k\) は小さい）
    よって全体として概ね \(O(\sqrt{g} + N\cdot k)\) に近い速度で動きます。
• 空間計算量: \(O(N)\)（入力の \(H,W,S\) 配列を保持）

実装のポイント

• 素因数分解は \(g\) に対してだけ行う：各 \(H_i, W_i\) を分解すると重すぎます。

• \(v_p(x)\)（\(p\) の指数）は、while x % p == 0: x//=p で数えます。調べる \(p\) が少ないので十分高速です。

• \(t=\left\lfloor\frac{a+b-c}{2}\right\rfloor\) の形になるため、最後は 2 で割って切り捨てる必要があります（コードでは // 2）。

• 入力が大きいので、sys.stdin.buffer.read() でまとめて読むと安全です。

  ソースコード

import sys
import math

def factorize_with_exp(n: int):
    factors = []
    if n % 2 == 0:
        e = 0
        while n % 2 == 0:
            n //= 2
            e += 1
        factors.append((2, e))
    p = 3
    while p * p <= n:
        if n % p == 0:
            e = 0
            while n % p == 0:
                n //= p
                e += 1
            factors.append((p, e))
        p += 2
    if n > 1:
        factors.append((n, 1))
    return factors

def v_p(x: int, p: int) -> int:
    c = 0
    while x % p == 0:
        x //= p
        c += 1
    return c

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return
    N = data[0]
    H = [0] * N
    W = [0] * N
    S = [0] * N

    g = 0
    idx = 1
    for i in range(N):
        h = data[idx]; w = data[idx + 1]; s = data[idx + 2]
        idx += 3
        H[i] = h
        W[i] = w
        S[i] = s
        g = math.gcd(g, h)
        g = math.gcd(g, w)

    if g == 1:
        print(1)
        return

    factors = factorize_with_exp(g)

    ans = 1
    for p, e0 in factors:
        e = e0  # must not exceed gcd exponent
        for i in range(N):
            a = v_p(H[i], p)
            b = v_p(W[i], p)
            c = v_p(S[i], p)
            t = (a + b - c) // 2
            if t < e:
                e = t
                if e == 0:
                    break
        ans *= pow(p, e)

    print(ans)

if __name__ == "__main__":
    main()

---

この解説は gpt-5.2-high によって生成されました。