Overview

We want to find the maximum side length \(d\) of a square tile that can tile all rooms, while also satisfying the condition that “the number of tiles used in each room \(i\) is a multiple of \(S_i\).”

Analysis

1) First, the “tileable” condition narrows down candidates for \(d\)

To tile room \(i\) with squares of side length \(d\), both \(H_i\) and \(W_i\) must be multiples of \(d\).
This means \(d\) must divide all \(H_i\) and \(W_i\), so: [ d \mid \gcd(H_1,W_1,H_2,W_2,\dots,H_N,W_N) ] If we define: [ g=\gcd(\text{all }H_i\text{ and all }W_i) ] then the candidates for \(d\) are limited to “divisors of \(g\).”

One could naively enumerate all divisors of \(g\) and check them in decreasing order, but the number of divisors of \(g\) can be quite large in the worst case, and checking \(N(=10^5)\) rooms for each divisor can become too slow.

2) Viewing the “tile count is a multiple of \(S_i\)” condition per prime factor

The number of tiles used in room \(i\) is: [ C_i=\frac{H_i}{d}\cdot\frac{W_i}{d}=\frac{H_iW_i}{d^2} ] and the condition is: [ S_i \mid C_i \quad\Longleftrightarrow\quad S_i \mid \frac{H_iW_i}{d^2} ]

This can be organized using the exponent of each prime \(p\) (how many times \(p\) divides a number). Let \(v_p(x)\) denote “the exponent of prime \(p\) in \(x\).” Then: [ v_p(C_i)=v_p(H_i)+v_p(W_i)-2v_p(d) ] so: [ S_i \mid C_i \quad\Longleftrightarrow\quad v_p(H_i)+v_p(W_i)-2v_p(d)\ \ge\ v_p(S_i) ] which means: [ 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 ]

In other words, for each prime \(p\), we can compute an upper bound on the exponent of \(p\) that can be included in \(d\) from each room, and we simply take the minimum over all rooms.

3) We only need to check primes that divide \(g\)

Since \(d \mid g\), the only primes that can appear in \(d\) are the prime factors of \(g\).
Therefore, we factorize \(g\) and determine the allowed exponent for each of its prime factors to construct the answer.

Algorithm

1. Compute the GCD of all \(H_i\) and \(W_i\): [ g=\gcd(H_1,W_1,H_2,W_2,\dots,H_N,W_N) ] If \(g=1\), the only possible \(d\) is \(1\), so the answer is \(1\).

2. Factorize \(g\) into the form \(g=\prod p^{e_0}\).

3. For each prime \(p\), determine the exponent \(e\) that can be included in \(d\):

   • Start with \(e=e_0\) (since \(d\mid g\), we cannot exceed this).
   • For each room \(i\), compute: [ 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 ] and update \(e=\min(e,t)\).
   • The final \(e\) is the exponent of that prime \(p\).

4. The answer is: [ d=\prod p^{e} ]

※ The constraints guarantee that “\(H_iW_i\) is a multiple of \(S_i\),” so \(d=1\) is always feasible, and the above computation is guaranteed to produce a valid solution (each \(t\) will not cause issues).

Complexity

• Time complexity:
  
  • Computing \(g\) is \(O(N\log \max(H_i,W_i))\)
    
  • Factorizing \(g\) is \(O(\sqrt{g})\)
    
  • Let \(k\) be the number of prime factors. Computing \(v_p\) for each room takes \(O(N\cdot k\cdot \log \max(H_i,W_i))\) (\(k\) is small)
    Overall, it runs at approximately \(O(\sqrt{g} + N\cdot k)\) speed.
• Space complexity: \(O(N)\) (storing the input arrays \(H, W, S\))

Implementation Notes

• Only factorize \(g\): Factorizing each \(H_i, W_i\) individually would be too expensive.

• \(v_p(x)\) (the exponent of \(p\)) is computed by while x % p == 0: x//=p and counting. Since the number of primes to check is small, this is sufficiently fast.

• Since the formula gives \(t=\left\lfloor\frac{a+b-c}{2}\right\rfloor\), we need to floor-divide by 2 at the end (in code, use // 2).

• Since the input is large, it is safer to read it all at once using sys.stdin.buffer.read().

  Source Code

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()

---

This editorial was generated by gpt-5.2-high.