← 返回题目列表

Codeforces · 1538/D

D. 关于除法的另一个问题

中文机器翻译题面 查看原题

给你两个整数 $$$a$$$ 和 $$$b$$$。在一轮中,您可以执行以下操作之一:

- 取一个整数 $$$c$$$ ($$$c > 1$$$ 且 $$$a$$$ 应能被 $$$c$$$ 整除)并将 $$$a$$$ 替换为 $$$\frac{a}{c}$$$;
- 取一个整数 $$$c$$$($$$c > 1$$$ 且 $$$b$$$ 应能被 $$$c$$$ 整除)并将 $$$b$$$ 替换为 $$$\frac{b}{c}$$$。

您的目标是使用 $$$k$$$ 回合使 $$$a$$$ 等于 $$$b$$$。

例如,在 $$$4$$$ 移动中,数字 $$$a=36$$$ 和 $$$b=48$$$ 可以相等:

- $$$c=6$$$,将 $$$b$$$ 除以 $$$c$$$ $$$\Rightarrow$$$ $$$a=36$$$,$$$b=8$$$;
- $$$c=2$$$,将 $$$a$$$ 除以 $$$c$$$ $$$\Rightarrow$$$ $$$a=18$$$,$$$b=8$$$;
- $$$c=9$$$,将 $$$a$$$ 除以 $$$c$$$ $$$\Rightarrow$$$ $$$a=2$$$,$$$b=8$$$;
- $$$c=4$$$,将 $$$b$$$ 除以 $$$c$$$ $$$\Rightarrow$$$ $$$a=2$$$,$$$b=2$$$。

对于给定的数字 $$$a$$$ 和 $$$b$$$,确定是否可以使用精确的 $$$k$$$ 轮数使它们相等。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$)。然后是 $$$t$$$ 测试用例。

每个测试用例包含三个整数 $$$a$$$、$$$b$$$ 和 $$$k$$$ ($$$1 \le a, b, k \le 10^9$$$)。

输出

对于每个测试用例输出:

- “是”,如果可以使数字 $$$a$$$ 和 $$$b$$$ 在 $$$k$$$ 轮次中完全相同;
- 否则“否”。

任何情况下都可以输出字符串“Yes”和“No”。

示例

输入 #1

8
36 48 2
36 48 3
36 48 4
2 8 1
2 8 2
1000000000 1000000000 1000000000
1 2 1
2 2 1

输出 #1

YES
YES
YES
YES
YES
NO
YES
NO