A14929 | Madoka and the Best School in Russia
时间限制1s
内存限制256MB
通过 / 提交0/0
题目描述
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!
- 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$ .
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).
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.
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.
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？
提交通过
评测结果：Accepted