CF1753B.Factorial Divisibility

普及/提高-

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

You are given an integer $x$ and an array of integers $a_1, a_2, \ldots, a_n$ . You have to determine if the number $a_1! + a_2! + \ldots + a_n!$ is divisible by $x!$ .

Here $k!$ is a factorial of $k$ — the product of all positive integers less than or equal to $k$ . For example, $3! = 1 \cdot 2 \cdot 3 = 6$ , and $5! = 1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 = 120$ .

输入格式

The first line contains two integers $n$ and $x$ ( $1 \le n \le 500\,000$ , $1 \le x \le 500\,000$ ).

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ( $1 \le a_i \le x$ ) — elements of given array.

输出格式

In the only line print "Yes" (without quotes) if $a_1! + a_2! + \ldots + a_n!$ is divisible by $x!$ , and "No" (without quotes) otherwise.

输入输出样例

输入#1
```
6 4
3 2 2 2 3 3
```
输出#1
```
Yes
```
输入#2
```
8 3
3 2 2 2 2 2 1 1
```
输出#2
```
Yes
```
输入#3
```
7 8
7 7 7 7 7 7 7
```
输出#3
```
No
```
输入#4
```
10 5
4 3 2 1 4 3 2 4 3 4
```
输出#4
```
No
```
输入#5
```
2 500000
499999 499999
```
输出#5
```
No
```

说明/提示

In the first example $3! + 2! + 2! + 2! + 3! + 3! = 6 + 2 + 2 + 2 + 6 + 6 = 24$ . Number $24$ is divisible by $4! = 24$ .

In the second example $3! + 2! + 2! + 2! + 2! + 2! + 1! + 1! = 18$ , is divisible by $3! = 6$ .

In the third example $7! + 7! + 7! + 7! + 7! + 7! + 7! = 7 \cdot 7!$ . It is easy to prove that this number is not divisible by $8!$ .

首页