GCDロボット
题意翻译
高桥君有$N$台机器人。机器人被编号$1,2, ... N$。机器人可以作出一些判断——“很像”或“不像”。每个机器人有$1$个正整数,号码为$i$的机器人里的数为$a[i]$。把$X,Y$两个数给编号为$i$的机器人判断,若$gcd(X,a[i])=gcd(Y,a[i])$,它就说“很像”、否则说“不像”。注意,在这个问题中$gcd(X,Y$)是$X$和$Y$的最大公约数。
关于正整数$X, Y$,当$N$台机器人都说“很像”时,就认为$X,Y$“完全一样”。
给出正整数$Z$,求与$Z$“完全一样”的数里面最小的数。
题目描述
[problemUrl]: https://atcoder.jp/contests/ddcc2017-final/tasks/ddcc2017_final_b
高橋君は $ 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 $ とそっくりさんな数のうち、もっとも小さいものを求めてください。
输入输出格式
输入格式
入力は以下の形式で標準入力から与えられる。
> $ N $ $ Z $ $ a_1 $ $ a_2 $ ... $ a_N $
输出格式
求めた答えを出力してください。
输入输出样例
输入样例 #1
3 12
2 6 9
输出样例 #1
6
输入样例 #2
10 1000000007
1 2 3 4 5 6 7 8 9 10
输出样例 #2
1
输入样例 #3
2 1000000000000000000
1000000000000000000 1000000000000000000
输出样例 #3
1000000000000000000
说明
### 制約
- $ 1\ ≦\ N\ ≦\ 100,000 $
- $ 1\ ≦\ Z,\ a_i\ ≦\ 10^{18} $
### Sample Explanation 1
\- $ {\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 $ が答えとなります。