codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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!$.