B - GCDロボット
Editorial
/


Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 500 点
問題文
高橋君は N 台のロボットを持っています。ロボットには番号 1, 2, ..., N がついています。
ロボットにはそれぞれ正整数が 1 つ書かれており、番号 i のロボットには a_i が書かれています。
番号 i のロボットは、正整数 X, Y を渡すと、{\rm gcd}(X, a_i) = {\rm gcd}(Y, a_i) ならば「似てる」、そうでないならば「似てない」と言います。なお、この問題では {\rm gcd}(X, Y) は X と Y の最大公約数とします。
正整数 X, Y について、N 台のロボット全てが「似てる」と言った時、X と Y はそっくりさんだとすることにします。
正整数 Z が与えられるので、Z とそっくりさんな数のうち、もっとも小さいものを求めてください。
制約
- 1 ≦ N ≦ 100,000
- 1 ≦ Z, a_i ≦ 10^{18}
入力
入力は以下の形式で標準入力から与えられる。
N Z a_1 a_2 ... a_N
出力
求めた答えを出力してください。
入力例 1
3 12 2 6 9
出力例 1
6
- {\rm gcd}(6, 2) = {\rm gcd}(12, 2) = 2
- {\rm gcd}(6, 6) = {\rm gcd}(12, 6) = 6
- {\rm gcd}(6, 9) = {\rm gcd}(12, 9) = 3
であるため、6 と 12 はそっくりさんであり、 また 6 より小さくて 12 とそっくりさんな数は存在しないため、6 が答えとなります。
入力例 2
10 1000000007 1 2 3 4 5 6 7 8 9 10
出力例 2
1
入力例 3
2 1000000000000000000 1000000000000000000 1000000000000000000
出力例 3
1000000000000000000