Type: Default 1000ms 256MiB

阶乘可除性

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

为了防止大家读太长的题干导致疲惫,此题题干贼短

题目描述

给定两个正整数 nnxx 和一个正整数序列 a1ana_1 \sim a_n

请问 a1!+a2!++an! a_1! + a_2! + \ldots + a_n! 是否能被 x!x! 整除。如果能则输出一个字符串 Yes\texttt{Yes},不能则输出字符串 No\texttt{No}

输入形式

第一行两个正整数 nnxx( 1n500000 1 \le n \le 500\,000 , 1x500000 1 \le x \le 500\,000 ).。

第二行 nn 个正整数 a1ana_1 \sim a_n( 1aix 1 \le a_i \le x )。

输出形式

一行一个字符串,输出 Yes \texttt{Yes}\ No \texttt{No}\

样例

6 4
3 2 2 2 3 3
Yes
8 3
3 2 2 2 2 2 1 1
Yes
7 8
7 7 7 7 7 7 7
No
10 5
4 3 2 1 4 3 2 4 3 4
No
2 500000
499999 499999
No

样例解释

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

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

在第三个样例中7!+7!+7!+7!+7!+7!+7!=77! 7! + 7! + 7! + 7! + 7! + 7! + 7! = 7 \cdot 7! . 很容易证明这个数字不能被 8! 8! 整除.

2022ACM新生积分赛 Round #6

Attended
Status
Done (Attended)
Rule
ACM/ICPC
Problem
10
Start at
2022-11-20 13:00
End at
2022-11-20 18:00
Duration
5 hour(s)
Host
Partic.
40