Задача №115157. Факториальная делимость
Вам дано число \(x\) и массив целых чисел \(a_1, a_2, \ldots, a_n\). Нужно определить, делится ли нацело число \(a_1! + a_2! + \ldots + a_n!\) на число \(x!\).
За \(k!\) мы обозначили факториал числа \(k\) — произведение всех натуральных чисел, меньших либо равных \(k\). Например \(3! = 1 \cdot 2 \cdot 3 = 6\), а \(5! = 1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 = 120\).
Первая строка содержит два целых числа \(n\) и \(x\) (\(1 \le n \le 500\,000\), \(1 \le x \le 500\,000\)).
Вторая строка содержит \(n\) целых чисел \(a_1, a_2, \ldots, a_n\) (\(1 \le a_i \le x\)) — элементы массива.
В единственной строке выведите « Yes » (без кавычек), если \(a_1! + a_2! + \ldots + a_n!\) делится нацело на \(x!\), и « No » (без кавычек) в противном случае.
В первом примере из условия \(3! + 2! + 2! + 2! + 3! + 3! = 6 + 2 + 2 + 2 + 6 + 6 = 24\). Число \(24\) делится на \(4! = 24\).
Во втором примере из условия \(3! + 2! + 2! + 2! + 2! + 2! + 1! + 1! = 18\), что делится на \(3! = 6\).
В третьем примере из условия \(7! + 7! + 7! + 7! + 7! + 7! + 7! = 7 \cdot 7!\). Нетрудно доказать, что это число не делится на \(8!\).
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