← 返回题目列表

AtCoder · awc0060_c

C. 同时烟花发射

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

分数: 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 被称为 公倍数 of T_1, T_2, \ldots, T_N if \frac{L}{T_i} 是所有的正整数 i (1 \leq i \leq N)。公倍数始终存在(例如,适当的正整数倍 T_1 \times T_2 \times \cdots \times T_N 是一个公倍数),所有公倍数中最小的称为 最小公倍数。这是整数最小公倍数的自然扩展。

所需时间等于最小公倍数 L of T_1, T_2, \ldots, T_N。查找 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

第一行包含一个整数 N 代表发射器的数量。以下每一项 N 行包含分子 P_i 和分母 Q_i 代表启动间隔 启动器的 T_i = \frac{P_i}{Q_i} 发射器的 i,用空格分隔。

输出

表示最小公倍数 L 作为不可约分数 \frac{A}{B} (A, B 是正整数, \gcd(A, B) = 1),并输出 A 和 B 在一行上用空格分隔。如果 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