← 返回题目列表

AtCoder · arc124_c

C. GCD 的 LCM

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

分数: 500 点

问题陈述

我们有一个红色袋子,一个蓝色袋子,和 N 卡包。最初,两个袋子都是空的。 每个卡包包含两张写有整数的卡片。我们知道 i第一个卡包包含一张带有 a_i 和另一个 b_i.

对于每个卡包,我们会将其中一张卡放入红色袋中,另一张放入蓝色袋中。

将所有卡片放入袋子后,让 X 是红色袋子里的卡片上写的所有整数的最大公约数。同样,让 Y 是蓝色袋子里的卡片上写的所有整数的最大公约数。 我们的分数将是最小公倍数 X 和 Y.

找到可能的最大分数。

约束

  • 输入中的所有值都是整数。
  • 1 \leq N \leq 50
  • 1 \leq a_i, b_i \leq 10^9

输入

输入由标准输入按以下格式给出:

N
a_1 b_1
\vdots
a_N b_N

输出

打印可能的最大分数。


示例输入 1

2
2 15
10 6

示例输出 1

10
  • 一个最佳的举动是将牌与 2 在红色袋子里,卡片上有 15 在蓝色袋子里,卡片上有 6 在红色袋子里,以及带有 10 在蓝色袋子里。
  • 那么,红色袋子里的卡片上写的所有整数的最大公约数将是 2,蓝色袋子里的卡片上写的所有整数的最大公约数将是 5.
  • 这里的分数将为 10.

示例输入 2

5
148834018 644854700
947642099 255192490
35137537 134714230
944287156 528403260
68656286 200621680

示例输出 2

238630

示例输入 3

20
557057460 31783488
843507940 794587200
640711140 620259584
1901220 499867584
190122000 41414848
349507610 620259584
890404700 609665088
392918800 211889920
507308870 722352000
156850650 498904448
806117280 862969856
193607570 992030080
660673950 422816704
622015810 563434560
207866720 316871744
63057130 117502592
482593010 366954816
605221700 705015552
702500790 900532160
171743540 353470912

示例输出 3

152594452160