309232: CF1647D. Madoka and the Best School in Russia

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Madoka and the Best School in Russia

题意翻译

- 如果 $n$ 是 $d$ 的倍数,则称 $n$ 为“好数”; - 如果 $n$ 是“好数”且不能写成任意两个“好数”之积,则称 $n$ 是“美丽数”。 $T$ 组询问,每组询问给定两个正整数 $x,d$,保证 $x$ 是好数,问 $x$ 是否有至少两种方式写为至少一个“美丽数”之积。如果是,输出 `YES`;否则输出 `NO`。 注意输出对大小写不敏感。 ### 输入格式 第一行一个正整数 $T$ 表示数据组数。 对于每组数据,有两个正整数 $x,d$。 ### 输出格式 对于每组数据,如果可以,输出 `YES`,否则输出 `NO`。

题目描述

Madoka is going to enroll in "TSUNS PTU". But she stumbled upon a difficult task during the entrance computer science exam: - A number is called good if it is a multiple of $ d $ . - A number is called beatiful if it is good and it cannot be represented as a product of two good numbers. Notice that a beautiful number must be good. Given a good number $ x $ , determine whether it can be represented in at least two different ways as a product of several (possibly, one) beautiful numbers. Two ways are different if the sets of numbers used are different. Solve this problem for Madoka and help her to enroll in the best school in Russia!

输入输出格式

输入格式


The first line contains a single integer $ t $ ( $ 1 \leq t \leq 100 $ ) — number of test cases. Below comes their description. Each test case consists of two integers $ x $ and $ d $ , separated by a space ( $ 2 \leq x, d \leq 10^9 $ ). It is guaranteed that $ x $ is a multiple of $ d $ .

输出格式


For each set of input data, output "NO" if the number cannot be represented in at least two ways. Otherwise, output "YES". You can output each letter in any case (for example, "YES", "Yes", "yes", "yEs", "yEs" will be recognized as a positive answer).

输入输出样例

输入样例 #1

8
6 2
12 2
36 2
8 2
1000 10
2376 6
128 4
16384 4

输出样例 #1

NO
NO
YES
NO
YES
YES
NO
YES

说明

In the first example, $ 6 $ can be represented as $ 6 $ , $ 1 \cdot 6 $ , $ 2 \cdot 3 $ . But $ 3 $ and $ 1 $ are not a good numbers because they are not divisible by $ 2 $ , so there is only one way. In the second example, $ 12 $ can be represented as $ 6 \cdot 2 $ , $ 12 $ , $ 3 \cdot 4 $ , or $ 3 \cdot 2 \cdot 2 $ . The first option is suitable. The second is— no, because $ 12 $ is not beautiful number ( $ 12 = 6 \cdot 2 $ ). The third and fourth are also not suitable, because $ 3 $ is not good number. In the third example, $ 36 $ can be represented as $ 18 \cdot 2 $ and $ 6 \cdot 6 $ . Therefore it can be decomposed in at least two ways.

Input

题意翻译

- 如果 $n$ 是 $d$ 的倍数,则称 $n$ 为“好数”; - 如果 $n$ 是“好数”且不能写成任意两个“好数”之积,则称 $n$ 是“美丽数”。 $T$ 组询问,每组询问给定两个正整数 $x,d$,保证 $x$ 是好数,问 $x$ 是否有至少两种方式写为至少一个“美丽数”之积。如果是,输出 `YES`;否则输出 `NO`。 注意输出对大小写不敏感。 ### 输入格式 第一行一个正整数 $T$ 表示数据组数。 对于每组数据,有两个正整数 $x,d$。 ### 输出格式 对于每组数据,如果可以,输出 `YES`,否则输出 `NO`。

加入题单

上一题 下一题 算法标签: