Codeforces Round 900 (Div. 3) |
---|
Закончено |
Василий - умный студент, и его преподаватель дискретной математики Соня хорошо преподала ему теорию чисел.
Он дал Огнену положительное целое число $$$n$$$.
Обозначим $$$d(n)$$$ как количество положительных делителей числа $$$n$$$, а $$$gcd(a, b)$$$ как наибольшее целое число $$$g$$$, такое что $$$a$$$ делится на $$$g$$$ и $$$b$$$ делится на $$$g$$$.
После этого он дал Огнену $$$q$$$ запросов, и есть $$$2$$$ типа запросов.
Обратите внимание, что $$$n$$$ не возвращается к своему исходному значению после запроса типа 1.
Поскольку Огнен боится теории чисел, Василий обещал ему, что после каждого запроса $$$d(n) \le 10^9$$$, однако, даже с таким ограничением, ему все равно нужна ваша помощь с этой задачей.
Первая строка содержит положительное целое число $$$t$$$, ($$$1 \le t \le 100$$$) — количество наборов входных данных.
Первая строка каждого набора содержит $$$2$$$ целых числа, $$$n$$$ и $$$q$$$ ($$$1 \le n \le 10^{6}$$$, $$$1\le q \le 1000$$$) — число $$$n$$$ и количество запросов.
Следующие $$$q$$$ строк содержат целое число $$$k$$$ ($$$1 \le k \le 2$$$), если $$$k=1$$$, то в этой строке есть еще одно целое число $$$x$$$ ($$$1 \le x \le 10^6$$$) — описание запросов.
Гарантируется, что для данного ввода $$$d(n)$$$ в любой момент не превышает $$$10^9$$$.
Гарантируется, что сумма $$$q$$$ по всем наборам входных данных не превышает $$$10^3$$$.
Для каждого запроса типа 1, вы должны вывести «YES», если существует такое положительное $$$a$$$, что $$$gcd(a, n) = 1$$$ и $$$d(n \cdot a)=n$$$, и «NO» в противном случае.
Вы можете вывести ответ в любом регистре (например, строки «yEs», «yes», «Yes», и «YES» будут распознаны как положительный ответ).
71 51 11 221 81 920 41 321 71 1216 101 61 61 101 91 11 91 71 31 21 109 11 38 11 28 31 51 81 1011 51 81 21 11 31 1
YES YES YES YES YES NO YES YES NO YES YES YES NO YES NO YES YES NO NO YES NO NO YES NO NO NO NO
В первом наборе примера, изначально $$$n=1$$$.
После первого запроса: $$$n=1$$$, $$$d(n)=1$$$, поэтому, взяв $$$a = 1$$$, $$$d(n \cdot a) = n$$$, и ответ на этот запрос «YES».
После второго запроса: $$$n=2$$$, $$$d(n)=2$$$, мы можем снова взять $$$a = 1$$$, $$$d(n \cdot a) = n$$$, и ответ на этот запрос «YES».
После третьего запроса $$$n=1$$$, и это запрос типа $$$2$$$, поэтому мы не отвечаем на него.
После четвертого запроса: $$$n=8$$$, и взяв $$$a=3$$$, $$$d(n \cdot a) = d(24) = 8 = n$$$, поэтому ответ «YES».
После пятого запроса: $$$n=72$$$, теперь мы можем взять $$$a=637$$$, чтобы получить $$$n \cdot a = 45864$$$, и $$$d(n \cdot a) = 72 = n$$$, поэтому ответ «YES».
Во втором наборе примера, изначально $$$n=20$$$.
После первого запроса: $$$n=60$$$, и ответ «YES».
После второго запроса: $$$n=20$$$, это запрос типа $$$2$$$, поэтому мы не отвечаем на него.
После третьего запроса: $$$n=140$$$, и можно доказать, что независимо от того, какое положительное целое число $$$a$$$ мы возьмем, $$$d(n \cdot a)$$$ никогда не будет равно $$$n$$$, поэтому ответ на этот запрос «NO».
После четвертого запроса: $$$n=1680$$$. Можно доказать, что существует положительное целое число $$$a$$$, такое что $$$d(n \cdot a) = n$$$, поэтому ответ «YES».
Название |
---|