1753B.md (1584B)
1 Source: https://codeforces.com/problemset/problem/1753/B 2 3 B. Factorial Divisibility 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 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!$. 22 23 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$. 24 25 Input 26 27 The first line contains two integers $n$ and $x$ ($1 \le n \le 500\,000$, $1 \le x \le 500\,000$). 28 29 The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le x$) — elements of given array. 30 31 Output 32 33 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. 34 35 Examples 36 37 Input 38 39 ``` 40 6 4 41 3 2 2 2 3 3 42 ``` 43 44 Output 45 46 ``` 47 Yes 48 ``` 49 50 Input 51 52 ``` 53 8 3 54 3 2 2 2 2 2 1 1 55 ``` 56 57 Output 58 59 ``` 60 Yes 61 ``` 62 63 Input 64 65 ``` 66 7 8 67 7 7 7 7 7 7 7 68 ``` 69 70 Output 71 72 ``` 73 No 74 ``` 75 76 Input 77 78 ``` 79 10 5 80 4 3 2 1 4 3 2 4 3 4 81 ``` 82 83 Output 84 85 ``` 86 No 87 ``` 88 89 Input 90 91 ``` 92 2 500000 93 499999 499999 94 ``` 95 96 Output 97 98 ``` 99 No 100 ``` 101 102 Note 103 104 In the first example $3! + 2! + 2! + 2! + 3! + 3! = 6 + 2 + 2 + 2 + 6 + 6 = 24$. Number $24$ is divisible by $4! = 24$. 105 106 In the second example $3! + 2! + 2! + 2! + 2! + 2! + 1! + 1! = 18$, is divisible by $3! = 6$. 107 108 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!$.