大きさ \(d\) のタイルで全ての部屋を敷き詰められることは、\(d\) が全ての \(i\) で \(H_i,W_i\) の約数であることと同値です。よってこの条件は、\(d\) が \(\gcd(H_1,\dots,H_N,W_1,\dots,W_N)\) の約数であることと同値です。

部屋 \(i\) を敷き詰めるタイルの枚数が \(S_i\) の倍数であることは、「ある整数 \(k\) が存在して \(\frac{H_iW_i}{d^2}=kS_i\) となること」であり、 \(S_i\) が \(H_iW_i\) の約数であることからこれは「ある整数 \(k\) が存在して \(\frac{H_iW_i}{S_i}=kd^2\) となること」、即ち「\(d^2\) が \(\frac{H_iW_i}{S_i}\) の約数であること」と同値です。よって、全ての \(i\) でこれが成り立つことは「\(d^2\) が \(\gcd(\frac{H_1W_1}{S_1},\dots,\frac{H_NW_N}{S_N})\) の約数であること」と同値です。

以上より

• \(d\) は \(\gcd(H_1,\dots,H_N,W_1,\dots,W_N)\) の約数
• \(d^2\) は \(\gcd(\frac{H_1W_1}{S_1},\dots,\frac{H_NW_N}{S_N})\) の約数

の 2 条件が必要十分であることがわかりました。

\(M=\max(H_1,\dots,H_N,W_1,\dots,W_N)\) として、 gcd の計算に \(O(N+\log M)\) 、 1 番目の条件を満たす \(d\) の列挙に \(O(\sqrt{M})\) 、それらそれぞれに対して 2 番目の条件を満たすか判定するのに各 \(O(1)\) であることから、 \(O(N+\sqrt{M})\) で答えを求めることができます。

実装例 (C++)

#include<bits/stdc++.h>
using namespace std;

int main(){
  int g1 = 0;
  long long g2 = 0;
  
  int n;
  cin >> n;
  for(int i=0; i<n; i++){
    int h, w, s;
    cin >> h >> w >> s;
    g1 = __gcd(g1, __gcd(h, w));
    g2 = __gcd(g2, (long long)h*w/s);
  }
  
  vector<int> d;
  for(int i=1; i*i<=g1; i++){
    if(g1 % i == 0){
      d.push_back(i);
      d.push_back(g1/i);
    }
  }
  
  int ans = 1;
  for(auto x: d){
    if(g2 % ((long long)x*x) == 0){
      ans = max(ans, x);
    }
  }
  cout << ans << endl;
}

実装例 (Python)

import math

g1 = 0
g2 = 0
N = int(input())
for _ in range(N):
  H, W, S = map(int, input().split())
  g1 = math.gcd(g1, H, W)
  g2 = math.gcd(g2, H*W//S)

d=[]
for i in range(1, math.isqrt(g1)+1):
  if g1 % i == 0:
    d.append(i)
    d.append(g1//i)

print(max(x for x in d if g2 % (x*x) == 0))