← 返回题目列表

Codeforces · 1753/B

B. 阶乘整除

中文机器翻译题面 查看原题

给定一个整数 $$$x$$$ 和一个整数数组 $$$a_1, a_2, \ldots, a_n$$$。您必须确定数字是否为 $$$a_1! +a_2! + \ldots + a_n!$$$ 可以被 $$$x!$$$ 整除。

这里 $$$k!$$$ 是 $$$k$$$ 的阶乘 — 所有小于或等于 $$$k$$$ 的正整数的乘积。例如,$$$3! = 1 \cdot 2 \cdot 3 = 6$$$ 和 $$$5! = 1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 = 120$$$。

输入

第一行包含两个整数 $$$n$$$ 和 $$$x$$$ ($$$1 \le n \le 500\,000$$$, $$$1 \le x \le 500\,000$$$)。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le x$$$) — 给定数组的元素。

输出

在唯一的行中打印“Yes”(不带引号)if $$$a_1! +a_2! + \ldots + a_n!$$$ 可以被 $$$x!$$$ 整除,否则为“否”(不带引号)。

示例

输入 #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

注意

在第一个示例中$$$3! + 2! + 2! + 2! + 3! + 3! = 6 + 2 + 2 + 2 + 6 + 6 = 24$$$。数字 $$$24$$$ 可以被 $$$4 整除! = 24$$$。

在第二个示例中$$$3! + 2! + 2! + 2! + 2! + 2! + 1! + 1! = 18$$$,可以被$$$3整除! = 6$$$。

在第三个例子中$$$7! + 7! + 7! + 7! + 7! + 7! + 7! = 7 \cdot 7!$$$。很容易证明这个数不能被$$$8!$$$整除。