← 返回题目列表

AtCoder · awc0101_d

D. 平铺计划

中文机器翻译题面 查看原题

分数: 400 分

问题陈述

高桥在一家装修公司工作,负责用方形瓷砖覆盖房间地板。

高桥已收到要求铺设地板的请求 N 矩形房间。的地板 i第一个房间有高度 H_i 和宽度 W_i.

高桥想要选择 正是一种类型的方形瓷砖 并用它来覆盖 所有房间楼层。在每个房间中,瓷砖均平行于房间边缘放置,没有间隙或重叠。正方形瓷砖的边长必须是正整数。

边长为正方形的瓷砖的充要条件 d 能够给房间的地板铺瓷砖 i 是两者 H_i 和 W_i 是以下的倍数 d。在这种情况下,房间中使用的瓷砖数量 i is C_i = \frac{H_i}{d} \times \frac{W_i}{d}.

此外,由于设计要求,每个房间都有指定的“设计系数” S_i。瓷砖数量 C_i 用于房间 i 必须是以下的倍数 S_i.

高桥想要使用尽可能大的瓷砖。求最大边长 d 一块方形瓷砖同时满足所有房间的上述条件。

约束

  • 1 \leq N \leq 10^5
  • 1 \leq H_i \leq 10^9
  • 1 \leq W_i \leq 10^9
  • 1 \leq S_i \leq 10^9
  • 对于所有人 i, H_i \times W_i 是的倍数 S_i (这保证 d = 1 总是满足条件,所以答案总是存在)
  • 所有输入均为整数

输入

N
H_1 W_1 S_1
H_2 W_2 S_2
\vdots
H_N W_N S_N
  • 第一行包含一个整数 N 代表房间数量。
  • 从第 2 行到 (N + 1)第行,给出了每个房间的信息。
  • 的 (1 + i)第行包含高度 H_i,宽度 W_i和设计系数 S_i 的 i第一个房间,以空格分隔。

输出

一行输出边长的最大值 满足条件的方形瓷砖的 d 。


示例输入 1

2
6 8 6
10 12 15

示例输出 1

2

示例输入 2

1
12 12 8

示例输出 2

3

示例输入 3

6
48 72 8
90 60 25
84 126 14
108 144 12
150 210 35
66 132 11

示例输出 3

6

示例输入 4

15
123456000 789000000 96
250000000 400000000 125000000
999999000 888888000 27
314159000 271828000 4
500001000 700002000 9
655360000 131072000 1024
100003000 300009000 3
777777000 222222000 6
12345000 67890000 15
987654000 321000000 18
400000000 600000000 100000000
864000000 972000000 7776
135790000 246800000 10000
999000000 1000000000 999
720720000 840840000 1001

示例输出 4

200

示例输入 5

1
1000000000 1000000000 1000000000

示例输出 5

10000