/ 
Time Limit: 4 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
赤い袋と青い袋と N 個のカードパックがあります。はじめどちらの袋も空です。 それぞれのカードパックには整数が書かれた 2 枚のカードが封入されており、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 が書かれたカードを青い袋に入れるのが最適な入れ方の 1 つです。
- このとき、赤い袋に入ったカードに書かれた整数全体の最大公約数は 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
Score : 500 points
Problem Statement
We have a red bag, a blue bag, and N card packs. Initially, both bags are empty. Each card pack contains two cards with integers written on them. We know that the i-th card pack contains a card with a_i and another with b_i.
For each card pack, we will put one of its cards in the red bag, and the other in the blue bag.
After we put all cards in the bags, let X be the greatest common divisor of all integers written on cards in the red bag. Similarly, let Y be the greatest common divisor of all integers written on cards in the blue bag. Our score will be the least common multiple of X and Y.
Find the maximum possible score.
Constraints
- All values in input are integers.
- 1 \leq N \leq 50
- 1 \leq a_i, b_i \leq 10^9
Input
Input is given from Standard Input in the following format:
N a_1 b_1 \vdots a_N b_N
Output
Print the maximum possible score.
Sample Input 1
2 2 15 10 6
Sample Output 1
10
- One optimal move is to put the card with 2 in the red bag, the card with 15 in the blue bag, the card with 6 in the red bag, and the card with 10 in the blue bag.
- Then, the greatest common divisor of all integers written on cards in the red bag will be 2, and the greatest common divisor of all integers written on cards in the blue bag will be 5.
- The score here will be 10.
Sample Input 2
5 148834018 644854700 947642099 255192490 35137537 134714230 944287156 528403260 68656286 200621680
Sample Output 2
238630
Sample Input 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
Sample Output 3
152594452160