Factorial Divisibility
题意翻译
### 题面翻译
给定两个正整数 $n$ 和 $x$ 和一个正整数序列 $a_1 \sim a_n$。
请问 $\sum_{i = 1}^n a_i!$ 是否能被 $x!$ 整除。如果能则输出一个字符串 $\texttt{Yes}$,不能则输出字符串 $\texttt{No}$。
### 输入格式
第一行两个正整数 $n$ 和 $x$。
第二行 $n$ 个正整数 $a_1 \sim a_n$。
### 输出格式
一行一个字符串,输出 $\texttt{Yes}$ 或 $\texttt{No}$。
题目描述
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! $ .