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