概要

\(N\) 個の長方形の部屋すべてを1種類の正方形タイル（一辺 \(d\)）で敷き詰め、かつ各部屋のタイル枚数がデザイン係数 \(S_i\) の倍数になるような最大の \(d\) を求める問題です。

考察

条件の整理

一辺 \(d\) のタイルが条件を満たすには、各部屋 \(i\) について：

1. 敷き詰め条件: \(d \mid H_i\) かつ \(d \mid W_i\)（タイルがぴったり収まる）
2. デザイン条件: \(S_i \mid \frac{H_i}{d} \times \frac{W_i}{d}\)（枚数が \(S_i\) の倍数）

素因数ごとに独立に考える

\(d\) を最大化する問題を、各素因数 \(p\) ごとの指数 \(e = v_p(d)\)（\(d\) に含まれる \(p\) の指数）を最大化する問題に分解します。

各部屋 \(i\) について \(a = v_p(H_i)\), \(b = v_p(W_i)\), \(s = v_p(S_i)\) とおくと：

• 条件1: \(e \leq a\) かつ \(e \leq b\) → \(e \leq \min(a, b)\)
• 条件2: \((a - e) + (b - e) \geq s\) → \(e \leq \lfloor\frac{a + b - s}{2}\rfloor\)

したがって各素数 \(p\) に対する最大指数は： $\(e_{\max}(p) = \min_{i=1}^{N} \min\left(\min(a_i, b_i),\ \left\lfloor\frac{a_i + b_i - s_i}{2}\right\rfloor\right)\)$

どの素数を調べればよいか

条件1より \(e \leq \min(a_i, b_i)\) が全部屋で成り立つ必要があるので、\(e \leq v_p(G)\) です。ここで \(G = \gcd(\gcd(H_1, W_1), \gcd(H_2, W_2), \ldots)\) です。

\(G\) を割らない素数 \(p\) については \(v_p(G) = 0\) なので \(e_{\max}(p) = 0\)、つまり \(d\) に寄与しません。\(G\) の素因数だけを調べれば十分です。

アルゴリズム

1. 全部屋の \(\gcd(H_i, W_i)\) の全体GCDとして \(G\) を計算する
2. \(G\) を素因数分解する
3. \(G\) の各素因数 \(p\) について、全部屋を走査して \(e_{\max}(p)\) を計算する
4. 答えは \(\prod_p p^{e_{\max}(p)}\)

具体例

部屋が1つで \(H=12, W=18, S=6\) の場合： - \(\gcd(12, 18) = 6\)、\(G = 6 = 2^1 \times 3^1\) - \(p=2\): \(a=v_2(12)=2, b=v_2(18)=1, s=v_2(6)=1\) - 条件1: \(e \leq \min(2,1) = 1\) - 条件2: \(e \leq \lfloor(2+1-1)/2\rfloor = 1\) - → \(e_{\max}(2) = 1\) - \(p=3\): \(a=v_3(12)=1, b=v_3(18)=2, s=v_3(6)=1\) - 条件1: \(e \leq \min(1,2) = 1\) - 条件2: \(e \leq \lfloor(1+2-1)/2\rfloor = 1\) - → \(e_{\max}(3) = 1\) - 答え: \(2^1 \times 3^1 = 6\)

計算量

• 時間計算量: \(O(N \cdot (\sqrt{G_{\max}} / \ln G_{\max} + P))\)
  • \(G\) の素因数分解に \(O(\sqrt{G})\)（\(G \leq 10^9\) なので高々 \(O(31623)\)）
  • \(G\) の異なる素因数の個数 \(P\) は高々約30個（\(2 \times 3 \times 5 \times \cdots < 10^9\)）
  • 各素数について全部屋の \(v_p\) を計算: 1部屋あたり \(O(\log_{p} V)\)
  • 全体: おおよそ \(O(N \times 30 \times 30) = O(N \cdot 900)\) 程度
• 空間計算量: \(O(N)\)

実装のポイント

• \(p\)-進付値 \(v_p(n)\) の計算は、\(n\) を \(p\) で割れる限り割り続ける単純なループで実装

• \(e_{\max}\) が0以下になったら早期にbreakして無駄な計算を省く

• \(G\) の素因数分解は \(G \leq 10^9\) なので試し割りで十分高速

• 制約で「\(d=1\) は常に条件を満たす」と保証されているため、答えが存在しない場合を心配する必要はない

  ソースコード

import sys
import math
from functools import reduce

def factorize(n):
    """Return prime factorization as dict {prime: exponent}"""
    factors = {}
    d = 2
    while d * d <= n:
        while n % d == 0:
            factors[d] = factors.get(d, 0) + 1
            n //= d
        d += 1
    if n > 1:
        factors[n] = factors.get(n, 0) + 1
    return factors

def solve():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    
    # For each room i, we need:
    # 1) d | H_i and d | W_i
    # 2) S_i | (H_i/d * W_i/d)
    #
    # Condition 1: d | gcd(H_i, W_i) for all i
    # So d | G where G = gcd of all gcd(H_i, W_i)
    #
    # Condition 2: For each room i, S_i | (H_i * W_i / d^2)
    # Let's think about this per prime p.
    #
    # For each prime p, let:
    #   a = v_p(H_i), b = v_p(W_i), s = v_p(S_i), e = v_p(d)
    #
    # Condition 1: e <= min(a, b) for all i => e <= v_p(G)
    # Condition 2: (a - e) + (b - e) >= s => e <= (a + b - s) / 2 for all i
    #
    # We want to maximize d, so for each prime p we want to maximize e = v_p(d).
    # e_max(p) = min over all i of: min(min(a_i, b_i), floor((a_i + b_i - s_i) / 2))
    # But also e >= 0.
    #
    # We only need to consider primes that appear in some H_i, W_i, or S_i.
    # Actually, we only need primes where the constraint might be binding.
    # Since d | G, we only care about primes dividing G.
    
    rooms = []
    G = 0  # gcd of all gcd(H_i, W_i)
    for i in range(N):
        H = int(input_data[idx]); idx += 1
        W = int(input_data[idx]); idx += 1
        S = int(input_data[idx]); idx += 1
        rooms.append((H, W, S))
        g = math.gcd(H, W)
        G = math.gcd(G, g) if i > 0 else g
    
    # Factorize G
    G_factors = factorize(G)
    
    # For each prime p dividing G, compute the max exponent e
    # e = min over all rooms of min(v_p(gcd(H_i,W_i)), floor((v_p(H_i)+v_p(W_i)-v_p(S_i))/2))
    # Note: v_p(gcd(H_i,W_i)) = min(v_p(H_i), v_p(W_i))
    
    def val_p(n, p):
        """p-adic valuation of n"""
        if n == 0:
            return float('inf')
        v = 0
        while n % p == 0:
            n //= p
            v += 1
        return v
    
    result = 1
    for p, vG in G_factors.items():
        # vG = min over all i of min(v_p(H_i), v_p(W_i))
        # This is the upper bound from condition 1
        e_max = vG  # already the global min from condition 1
        
        for H, W, S in rooms:
            a = val_p(H, p)
            b = val_p(W, p)
            s = val_p(S, p)
            
            # Condition 1 bound for this room: min(a, b) -- already captured in vG
            # Condition 2 bound: floor((a + b - s) / 2)
            bound2 = (a + b - s) // 2
            
            e_max = min(e_max, bound2)
            
            if e_max <= 0:
                e_max = 0
                break
        
        e_max = max(e_max, 0)
        result *= p ** e_max
    
    print(result)

solve()

---

この解説は claude4.6opus-thinking によって生成されました。