Codeforces Round 752 (Div. 1) |
---|
Закончено |
У YouKn0wWho есть последовательность целых чисел $$$a_1, a_2, \ldots, a_n$$$. Он будет выполнять следующую операцию, пока последовательность не станет пустой: выберет индекс $$$i$$$ такой, что $$$1 \le i \le |a|$$$ и $$$a_i$$$ не делится на $$$(i + 1)$$$, и удалит этот элемент из последовательности. Здесь $$$|a|$$$ — длина последовательности $$$a$$$ в момент выполнения операции. Обратите внимание, что последовательность $$$a$$$ меняется, и следующая операция выполняется над этой измененной последовательностью.
Например, если $$$a=[3,5,4,5]$$$, то можно выбрать $$$i = 2$$$, так как $$$a_2 = 5$$$ не делится на $$$i+1 = 3$$$. После этой операции последовательность будет $$$[3,4,5]$$$.
Помогите YouKn0wWho определить, можно ли удалить всю последовательность с помощью вышеупомянутой операции.
Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10\,000$$$) — количество наборов входных данных
Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 10^5$$$).
Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$).
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$3 \cdot 10^5$$$.
Для каждого набора входных данных выведите «YES» (без кавычек), если возможно удалить всю последовательность с помощью вышеупомянутой операции, выведите «NO» (без кавычек) в противном случае. Вы можете выводить каждую букву в любом регистре (верхнем или нижнем).
5 3 1 2 3 1 2 2 7 7 10 384836991 191890310 576823355 782177068 404011431 818008580 954291757 160449218 155374934 840594328 8 6 69 696 69696 696969 6969696 69696969 696969696
YES NO YES YES NO
В первом наборе входных данных YouKn0wWho может выполнить следующие операции (удаляемые элементы подчеркнуты): $$$[1, \underline{2}, 3] \rightarrow [\underline{1}, 3] \rightarrow [\underline{3}] \rightarrow [\,].$$$
Во втором наборе входных данных невозможно удалить всю последовательность, так как $$$i$$$ может быть только $$$1$$$, а когда $$$i=1$$$, $$$a_1 = 2$$$ делится на $$$i + 1 = 2$$$.
Название |
---|