分数: 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