C - Simultaneous Firework Launch Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 366 点

問題文

高橋君は花火大会の演出を担当しています。会場には N 台の花火発射装置が設置されており、それぞれ一定の間隔で花火を打ち上げます。

各発射装置 i（1 \leq i \leq N）の打ち上げ間隔は T_i 秒です。ただし、T_i は整数とは限らず、正の有理数として与えられます。具体的には、各 T_i は既約分数 \frac{P_i}{Q_i}（P_i, Q_i は正の整数、\gcd(P_i, Q_i) = 1）の形で入力されます。

すべての発射装置は時刻 0 に同時にスタートし、時刻 0 にも花火を打ち上げます。つまり、発射装置 i は時刻 0, T_i, 2T_i, 3T_i, \ldots に花火を打ち上げます。

高橋君はフィナーレの演出として、時刻 0 より後ですべての発射装置が同時に花火を打ち上げる最も早い時刻を知りたいと考えています。

ここで、正の有理数の組 T_1, T_2, \ldots, T_N に対する最小公倍数を次のように定義します。正の有理数 L が、すべての i（1 \leq i \leq N）に対して \frac{L}{T_i} が正の整数となるとき、L を T_1, T_2, \ldots, T_N の公倍数といいます。公倍数は必ず存在し（例えば T_1 \times T_2 \times \cdots \times T_N の適切な正整数倍は公倍数です）、公倍数のうち最小のものを最小公倍数といいます。これは整数における最小公倍数の自然な拡張です。

求める時刻は T_1, T_2, \ldots, T_N の最小公倍数 L に等しくなります。L を既約分数として求めてください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq P_i \leq 10^9
  • 1 \leq Q_i \leq 10^9
  • \gcd(P_i, Q_i) = 1
  • 入力で与えられる値はすべて整数である。
  • 答えを既約分数 \frac{A}{B}（A, B は正の整数、\gcd(A, B) = 1）で表したとき、A \leq 10^{18} かつ B \leq 10^{18} であることが保証される。

入力

N
P_1 Q_1
P_2 Q_2
\vdots
P_N Q_N

1 行目には、発射装置の台数を表す整数 N が与えられる。続く N 行のうち i 行目には、発射装置 i の打ち上げ間隔 T_i = \frac{P_i}{Q_i} を表す分子 P_i と分母 Q_i が、スペース区切りで与えられる。

出力

最小公倍数 L を既約分数 \frac{A}{B}（A, B は正の整数、\gcd(A, B) = 1）として、A と B をスペース区切りで 1 行に出力せよ。L が整数となる場合は B = 1 として出力せよ。

入力例 1

2
1 2
1 3

出力例 1

1 1

入力例 2

3
2 3
4 9
8 27

出力例 2

8 3

入力例 3

5
3 4
5 6
7 3
2 9
1 2

出力例 3

210 1

入力例 4

8
12 5
18 7
15 4
20 3
14 9
25 6
21 8
10 11

出力例 4

6300 1

入力例 5

1
999999937 1

出力例 5

999999937 1

Score : 366 pts

Problem Statement

Takahashi is in charge of directing a fireworks festival. At the venue, N firework launchers are installed, each launching fireworks at regular intervals.

The launch interval of each launcher i (1 \leq i \leq N) is T_i seconds. However, T_i is not necessarily an integer and is given as a positive rational number. Specifically, each T_i is given as an irreducible fraction \frac{P_i}{Q_i} (P_i, Q_i are positive integers, \gcd(P_i, Q_i) = 1).

All launchers start simultaneously at time 0 and also launch fireworks at time 0. That is, launcher i launches fireworks at times 0, T_i, 2T_i, 3T_i, \ldots.

For the finale, Takahashi wants to know the earliest time after time 0 at which all launchers simultaneously launch fireworks.

Here, the least common multiple of a set of positive rational numbers T_1, T_2, \ldots, T_N is defined as follows. A positive rational number L is called a common multiple of T_1, T_2, \ldots, T_N if \frac{L}{T_i} is a positive integer for all i (1 \leq i \leq N). Common multiples always exist (for example, an appropriate positive integer multiple of T_1 \times T_2 \times \cdots \times T_N is a common multiple), and the smallest among all common multiples is called the least common multiple. This is a natural extension of the least common multiple for integers.

The desired time equals the least common multiple L of T_1, T_2, \ldots, T_N. Find L as an irreducible fraction.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq P_i \leq 10^9
  • 1 \leq Q_i \leq 10^9
  • \gcd(P_i, Q_i) = 1
  • All values given in the input are integers.
  • It is guaranteed that when the answer is expressed as an irreducible fraction \frac{A}{B} (A, B are positive integers, \gcd(A, B) = 1), A \leq 10^{18} and B \leq 10^{18}.

Input

N
P_1 Q_1
P_2 Q_2
\vdots
P_N Q_N

The first line contains an integer N representing the number of launchers. Each of the following N lines contains the numerator P_i and denominator Q_i representing the launch interval T_i = \frac{P_i}{Q_i} of launcher i, separated by a space.

Output

Express the least common multiple L as an irreducible fraction \frac{A}{B} (A, B are positive integers, \gcd(A, B) = 1), and output A and B separated by a space on a single line. If L is an integer, output with B = 1.

Sample Input 1

2
1 2
1 3

Sample Output 1

1 1

Sample Input 2

3
2 3
4 9
8 27

Sample Output 2

8 3

Sample Input 3

5
3 4
5 6
7 3
2 9
1 2

Sample Output 3

210 1

Sample Input 4

8
12 5
18 7
15 4
20 3
14 9
25 6
21 8
10 11

Sample Output 4

6300 1

Sample Input 5

1
999999937 1

Sample Output 5

999999937 1