/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 333 点
問題文
高橋君は会社の総務部で働いています。今度、 N 人の社員が全員参加する会議を開催することになりました。
会社には M 個の会議室があり、各会議室には 1 から M までの番号が付けられています。
社員 i （ 1 \leq i \leq N ）には、スケジュールの都合により参加条件を表す正の整数 P_i が定まっています。社員 i は、番号が P_i の倍数である会議室に限り参加することができます。言い換えると、会議室 j に社員 i が参加できるのは、 j が P_i の倍数であるとき、またそのときに限ります。
高橋君は、すべての社員が参加できる会議室を見つけたいと考えています。すなわち、ある会議室の番号 j （ 1 \leq j \leq M ）であって、すべての社員 i （ 1 \leq i \leq N ）について j が P_i の倍数であるようなものが存在するかどうかを判定してください。
そのような会議室が存在する場合は Yes を、存在しない場合は No を出力してください。
制約
- 1 \leq N \leq 10^5
- 1 \leq M \leq 10^{18}
- 1 \leq P_i \leq 10^9
- 入力はすべて整数である
入力
N M P_1 P_2 \ldots P_N
- 1 行目には、社員の人数を表す整数 N と、会議室の数を表す整数 M が、スペース区切りで与えられる。
- 2 行目には、各社員の参加条件を表す N 個の整数 P_1, P_2, \ldots, P_N が、スペース区切りで与えられる。
出力
すべての社員が参加できる会議室が存在する場合は Yes を、存在しない場合は No を 1 行で出力してください。
入力例 1
3 12 2 3 4
出力例 1
Yes
入力例 2
4 100 6 10 15 3
出力例 2
Yes
入力例 3
5 1000000000000000000 12 18 24 36 48
出力例 3
Yes
入力例 4
3 50 7 11 13
出力例 4
No
Score : 333 pts
Problem Statement
Takahashi works in the general affairs department of a company. He needs to organize a meeting that all N employees must attend.
The company has M meeting rooms, numbered from 1 to M.
For each employee i (1 \leq i \leq N), due to scheduling constraints, there is a positive integer P_i representing their participation condition. Employee i can only attend in a meeting room whose number is a multiple of P_i. In other words, employee i can attend in meeting room j if and only if j is a multiple of P_i.
Takahashi wants to find a meeting room that all employees can attend. Specifically, determine whether there exists a meeting room number j (1 \leq j \leq M) such that j is a multiple of P_i for every employee i (1 \leq i \leq N).
If such a meeting room exists, output Yes; otherwise, output No.
Constraints
- 1 \leq N \leq 10^5
- 1 \leq M \leq 10^{18}
- 1 \leq P_i \leq 10^9
- All input values are integers.
Input
N M P_1 P_2 \ldots P_N
- The first line contains an integer N representing the number of employees and an integer M representing the number of meeting rooms, separated by a space.
- The second line contains N integers P_1, P_2, \ldots, P_N representing the participation conditions of each employee, separated by spaces.
Output
If there exists a meeting room that all employees can attend, output Yes; otherwise, output No, in a single line.
Sample Input 1
3 12 2 3 4
Sample Output 1
Yes
Sample Input 2
4 100 6 10 15 3
Sample Output 2
Yes
Sample Input 3
5 1000000000000000000 12 18 24 36 48
Sample Output 3
Yes
Sample Input 4
3 50 7 11 13
Sample Output 4
No