D - Tiling Plan Editorial /

Time Limit: 2 sec / Memory Limit: 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