Задача №114665. Целостный массив
Дан массив \(a\) из \(n\) целых положительных чисел, пронумерованных от \(1\) до \(n\). Назовём массив целостным , если для любых двух, не обязательно различных, чисел \(x\) и \(y\) из этого массива, для которых \(x \ge y\), число \(\left \lfloor \frac{x}{y} \right \rfloor\) (частное от деления \(x\) на \(y\) с округлением вниз) тоже лежит в этом массиве.
Известно, что в массиве \(a\) все числа не превосходят \(c\). Ваша задача — проверить, является ли данный массив целостным.
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится единственное целое число \(t\) (\(1 \le t \le 10\,000\)) — количество наборов входных данных. Далее следуют описания наборов входных данных.
Первая строка каждого набора входных данных содержит два целых числа \(n\) и \(c\) (\(1 \le n \le 10^6\), \(1 \le c \le 10^7\)) — размер массива \(a\) и ограничение на числа в массиве.
Вторая строка каждого набора входных данных содержит \(n\) целых чисел \(a_1\), \(a_2\), ..., \(a_n\) (\(1 \le a_i \le c\)) — элементы массива \(a\).
Пусть \(N\) обозначает сумму значений \(n\) по всем наборам входных данных, а \(C\) — сумму значений \(c\) по всем наборам входных данных. Гарантируется, что \(N \le 10^6\) и \(C \le 10^7\).
Для каждого набора входных данных выведите Yes , если массив является целостным, и No иначе.
В первом наборе входных данных нетрудно заметить, что массив является целостным:
- \(\left \lfloor \frac{1}{1} \right \rfloor = 1\), \(a_1 = 1\), число встречается в массиве
- \(\left \lfloor \frac{2}{2} \right \rfloor = 1\)
- \(\left \lfloor \frac{5}{5} \right \rfloor = 1\)
- \(\left \lfloor \frac{2}{1} \right \rfloor = 2\), \(a_2 = 2\), число встречается в массиве
- \(\left \lfloor \frac{5}{1} \right \rfloor = 5\), \(a_3 = 5\), число встречается в массиве
- \(\left \lfloor \frac{5}{2} \right \rfloor = 2\), \(a_2 = 2\), число встречается в массиве
Таким образом, условие выполнено, массив является целостным.
Во втором наборе входных данных достаточно заметить, что
\(\left \lfloor \frac{7}{3} \right \rfloor = \left \lfloor 2\frac{1}{3} \right \rfloor = 2\), этого числа нет в массиве \(a\), поэтому он не является целостным.
В третьем наборе входных данных \(\left \lfloor \frac{2}{2} \right \rfloor = 1\), но в массиве есть только число \(2\), поэтому он не является целостным.
Тесты к этой задаче состоят из 5 групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов необходимых групп.
| Доп. ограничения | |||||
| Группа | Баллы | \(n, m\) | \(s_i, t_i\) | Необх. группы | Комментарий |
| 0 | 0 | – | – | – | Тесты из условия. |
| 1 | 13 | \(N \le 100\) | – | 0 | |
| 2 | 17 | \(N \le 100\,000\) | \(C \le 10\,000\) | 0 | |
| 3 | 15 | \(N \le 1000\) | – | 0, 1 | |
| 4 | 27 | \(N \le 100\,000\) | – | 0 – 3 | |
| 5 | 28 | – | – | 0 – 4 | |
3 3 5 1 2 5 4 10 1 3 3 7 1 2 2
Yes No No