/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 400 点
問題文
高橋君はリフォーム会社で働いており、正方形のタイルを使って部屋の床を敷き詰める仕事をしています。
高橋君は N 個の長方形の部屋の床にタイルを張る依頼を受けました。i 番目の部屋の床の縦の長さは H_i、横の長さは W_i です。
高橋君は、ちょうど1種類の正方形タイルを選び、そのタイルを使ってすべての部屋の床を敷き詰めたいと考えています。各部屋において、タイルは部屋の辺に平行に隙間なく・重なりなく並べます。正方形タイルの一辺の長さは正の整数でなければなりません。
一辺の長さ d の正方形タイルで部屋 i の床を敷き詰められるための必要十分条件は、H_i と W_i がともに d の倍数であることです。このとき、部屋 i に使うタイルの枚数は C_i = \frac{H_i}{d} \times \frac{W_i}{d} 枚です。
さらに、各部屋にはデザイン上の都合により「デザイン係数」S_i が指定されています。部屋 i に使うタイルの枚数 C_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
- 1 行目には、部屋の数を表す整数 N が与えられる。
- 2 行目から N + 1 行目では、各部屋の情報が与えられる。
- 1 + i 行目には、i 番目の部屋の縦の長さ H_i、横の長さ W_i、デザイン係数 S_i がスペース区切りで与えられる。
出力
条件を満たす正方形タイルの一辺の長さ d の最大値を 1 行で出力せよ。
入力例 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
Score : 400 pts
Problem Statement
Takahashi works at a renovation company and is responsible for covering room floors with square tiles.
Takahashi has received requests to tile the floors of N rectangular rooms. The floor of the i-th room has height H_i and width W_i.
Takahashi wants to choose exactly one type of square tile and use it to cover all room floors. In each room, tiles are placed parallel to the room's edges without gaps or overlaps. The side length of the square tile must be a positive integer.
The necessary and sufficient condition for a square tile with side length d to be able to tile the floor of room i is that both H_i and W_i are multiples of d. In this case, the number of tiles used in room i is C_i = \frac{H_i}{d} \times \frac{W_i}{d}.
Furthermore, due to design requirements, each room has a specified "design coefficient" S_i. The number of tiles C_i used in room i must be a multiple of S_i.
Takahashi wants to use tiles that are as large as possible. Find the maximum side length d of a square tile that simultaneously satisfies the above conditions for all rooms.
Constraints
- 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
- For all i, H_i \times W_i is a multiple of S_i (this guarantees that d = 1 always satisfies the conditions, so an answer always exists)
- All inputs are integers
Input
N H_1 W_1 S_1 H_2 W_2 S_2 \vdots H_N W_N S_N
- The first line contains an integer N representing the number of rooms.
- From the 2nd line to the (N + 1)-th line, information about each room is given.
- The (1 + i)-th line contains the height H_i, width W_i, and design coefficient S_i of the i-th room, separated by spaces.
Output
Output in one line the maximum value of the side length d of a square tile that satisfies the conditions.
Sample Input 1
2 6 8 6 10 12 15
Sample Output 1
2
Sample Input 2
1 12 12 8
Sample Output 2
3
Sample Input 3
6 48 72 8 90 60 25 84 126 14 108 144 12 150 210 35 66 132 11
Sample Output 3
6
Sample Input 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
Sample Output 4
200
Sample Input 5
1 1000000000 1000000000 1000000000
Sample Output 5
10000