传统题 1000ms 256MiB

阶乘可除性

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

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

题目描述

给定两个正整数 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 $ . 数字 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

已参加
状态
已结束 (已参加)
规则
ACM/ICPC
题目
10
开始于
2022-11-20 13:00
结束于
2022-11-20 18:00
持续时间
5 小时
主持人
参赛人数
40