A16874. Divide and Conquer
编程题
入门
知识点
题目描述
给你两个正整数 $x$ 和 $y$。
你可以执行以下操作任意多次（包括零次）：
* 选择任意一个正整数 $z$，使得 $z$ 整除 $x$；
* 将 $x$ 更新为 $\frac{x}{z}$。
判断是否可以通过上述操作使 $x$ 恰好等于 $y$。
你可以执行以下操作任意多次（包括零次）：
* 选择任意一个正整数 $z$，使得 $z$ 整除 $x$；
* 将 $x$ 更新为 $\frac{x}{z}$。
判断是否可以通过上述操作使 $x$ 恰好等于 $y$。
输入格式
输入的第一行包含一个整数 $t$（$1 \le t \le 10^4$）—— 表示测试用例的数量。接下来是每个测试用例的描述。
每个测试用例仅有一行，包含两个以空格分隔的整数 $x$ 和 $y$（$1 \le x, y \le 100$）。
每个测试用例仅有一行，包含两个以空格分隔的整数 $x$ 和 $y$（$1 \le x, y \le 100$）。
输出格式
对于每个测试用例，如果可以使 $x$ 恰好等于 $y$，则输出 "YES"；否则输出 "NO"。
你可以以任意大小写形式输出 "YES" 和 "NO"（例如，字符串 "yEs"、"yes" 和 "Yes" 均被视为肯定回答）。
你可以以任意大小写形式输出 "YES" 和 "NO"（例如，字符串 "yEs"、"yes" 和 "Yes" 均被视为肯定回答）。
输入输出样例
输入 #1
3 12 2 6 7 99 79
输出 #1
YES NO NO
说明/提示
对于第一个测试用例：
* 选择 $z = 2$，则 $x = \frac{12}{2} = 6$
* 选择 $z = 3$，则 $x = \frac{6}{3} = 2$
因此，我们可以使 $x = y$。故输出 YES。
对于第二个测试用例，可以证明无法使 $x$ 等于 $y$。
* 选择 $z = 2$，则 $x = \frac{12}{2} = 6$
* 选择 $z = 3$，则 $x = \frac{6}{3} = 2$
因此，我们可以使 $x = y$。故输出 YES。
对于第二个测试用例，可以证明无法使 $x$ 等于 $y$。