Codeforces Round 777 (Div. 2) |
---|
Закончено |
Мадока собирается поступить в «ЦНУС ПТУ». Но на вступительном экзамене по информатике ей попалась сложная задача:
Обратите внимание, что красивое число обязано быть хорошим.
Дано хорошее число $$$x$$$. Требуется определить, можно ли его представить хотя бы двумя различными способами в виде произведения нескольких (возможно одного) красивых чисел. Два способа считаются различными, если в них отличаются множества используемых чисел.
Решите эту задачу за Мадоку и помогите ей поступить в лучшую школу России!
В первой строке дано единственное число $$$t$$$ ($$$1 \leq t \leq 100$$$) — количество тестовых случаев. Ниже идет их описание.
Каждый тестовый случай состоит из двух целых чисел $$$x$$$ и $$$d$$$, записанных через пробел ($$$2 \leq x, d \leq 10^9$$$). Гарантируется, что $$$x$$$ кратно $$$d$$$.
Для каждого набора входных данных выведите «NO», если число нельзя представить хотя бы двумя способами. Иначе, выведите «YES».
Вы можете выводить каждую букву в любом регистре (например, «YES», «Yes», «yes», «yEs» будут распознаны как положительный ответ).
86 212 236 28 21000 102376 6128 416384 4
NO NO YES NO YES YES NO YES
В первом примере $$$6$$$ можно представить в виде $$$6$$$, $$$1 \cdot 6$$$, $$$2 \cdot 3$$$. Но $$$3$$$ и $$$1$$$ не являются хорошими числами, поскольку не делятся на $$$2$$$, поэтому способ только один.
Во втором примере $$$12$$$ можно представить в виде $$$6 \cdot 2$$$, $$$12$$$, $$$3 \cdot 4$$$, или $$$3 \cdot 2 \cdot 2$$$. Первый вариант подходит. Второй — нет, так как $$$12$$$ не является красивым ($$$12 = 6 \cdot 2$$$). Третий и четвертый также не подходят, поскольку $$$3$$$ не являетcя хорошим.
В третьем примере $$$36$$$ можно представить в виде $$$18 \cdot 2$$$ и $$$6 \cdot 6$$$. Поэтому его можно разложить хотя бы двумя способами.
Название |
---|