Codeforces Round 868 (Div. 2) |
---|
Закончено |
Простое число — это целое число большее $$$1$$$, которое имеет ровно два делителя. Например, число $$$7$$$ простое, так как имеет два делителя $$$\{1, 7\}$$$. Составное число — это целое число большее $$$1$$$, которое имеет более двух различных делителей.
Обратите внимание, что число $$$1$$$ не является ни простым, ни составным.
Рассмотрим составное число $$$v$$$. Оно имеет несколько делителей: некоторые делители простые, остальные сами составные. Если число простых делителей числа $$$v$$$ меньше или равно числу составных делителей, назовем число $$$v$$$ сильно составным.
Например, число $$$12$$$ имеет $$$6$$$ делителей: $$$\{1, 2, 3, 4, 6, 12\}$$$, два делителя $$$2$$$ и $$$3$$$ — простые, в то время как три делителя $$$4$$$, $$$6$$$ и $$$12$$$ — составные. Поэтому, число $$$12$$$ сильно составное. Другие примеры сильно составных чисел: $$$4$$$, $$$8$$$, $$$9$$$, $$$16$$$ и так далее.
С другой стороны, делители числа $$$15$$$ — это $$$\{1, 3, 5, 15\}$$$: $$$3$$$ и $$$5$$$ простые, $$$15$$$ составное. Поэтому, число $$$15$$$ не сильно составное. Другие примеры: $$$2$$$, $$$3$$$, $$$5$$$, $$$6$$$, $$$7$$$, $$$10$$$ и так далее.
Вам даны $$$n$$$ чисел $$$a_1, a_2, \dots, a_n$$$ ($$$a_i > 1$$$). Вам необходимо построить массив $$$b_1, b_2, \dots, b_k$$$ который удовлетворяет следующим условиям:
Найдите размер $$$k$$$ массива $$$b$$$, или сообщите, что нет массива $$$b$$$ удовлетворяющего условиям.
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 1000$$$) — размер массива $$$a$$$.
Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots a_n$$$ ($$$2 \le a_i \le 10^7$$$) — сам массив $$$a$$$.
Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$1000$$$.
Для каждого набора входных данных выведите размер $$$k$$$ массива $$$b$$$, или $$$0$$$, если нет массива $$$b$$$ удовлетворяющего условиям.
823 633 4 522 333 10 14225 301108093 3 3 5 5 5 7 7 72012 15 2 2 2 2 2 3 3 3 17 21 21 21 30 6 6 33 31 39
1 1 0 2 2 3 4 15
В первом набор мы можем получить массив $$$b = [18]$$$: $$$a_1 \cdot a_2 = 18 = b_1$$$; $$$18$$$ является сильно составным числом.
Во втором наборе мы можем получить массив $$$b = [60]$$$: $$$a_1 \cdot a_2 \cdot a_3 = 60 = b_1$$$; $$$60$$$ является сильно составным числом.
В третьем наборе нет массива $$$b$$$ удовлетворяющего условиям.
В четвертом наборе мы можем получить массив $$$b = [4, 105]$$$: $$$a_1 \cdot a_2 \cdot a_3 = 420 = b_1 \cdot b_2$$$; $$$4$$$ и $$$105$$$ являются сильно составными числами.
Название |
---|