← 返回题目列表

Codeforces · 1542/B

B. 加和乘

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

有一个无限集生成如下:

- $$$1$$$ 在此集合中。
- 如果 $$$x$$$ 在这个集合中,则 $$$x \cdot a$$$ 和 $$$x+b$$$ 都在这个集合中。

例如,当 $$$a=3$$$ 且 $$$b=6$$$ 时,集合的五个最小元素为:

- $$$1$$$,
- $$$3$$$ ($$$1$$$ 在这个集合中,所以 $$$1\cdot a=3$$$ 在这个集合中),
- $$$7$$$ ($$$1$$$ 在这个集合中,所以 $$$1+b=7$$$ 在这个集合中),
- $$$9$$$ ($$$3$$$ 在这个集合中,所以 $$$3\cdot a=9$$$ 在这个集合中),
- $$$13$$$ ($$$7$$$ 在这个集合中,所以 $$$7+b=13$$$ 在这个集合中)。

给定正整数$$$a$$$、$$$b$$$、$$$n$$$,确定$$$n$$$是否在这个集合中。

输入

输入由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1\leq t\leq 10^5$$$) — 测试用例的数量。测试用例的描述如下。

描述每个测试用例的唯一行包含三个整数 $$$n$$$、$$$a$$$、$$$b$$$ ($$$1\leq n,a,b\leq 10^9$$$),并用一个空格分隔。

输出

对于每个测试用例,如果 $$$n$$$ 在此集合中,则打印“Yes”,否则打印“No”。您可以在任何情况下打印每个字母。

示例

输入 #1

5
24 3 5
10 3 6
2345 1 4
19260817 394 485
19260817 233 264

输出 #1

Yes
No
Yes
No
Yes

注意

在第一个测试用例中,$$$24$$$ 生成如下:

- $$$1$$$ 在这个集合中,所以 $$$3$$$ 和 $$$6$$$ 在这个集合中;
- $$$3$$$ 在这个集合中,所以 $$$9$$$ 和 $$$8$$$ 在这个集合中;
- $$$8$$$ 在这个集合中,所以 $$$24$$$ 和 $$$13$$$ 在这个集合中。

因此我们可以看到 $$$24$$$ 在这个集合中。

第二个测试用例中集合的五个最小元素在语句中进行了描述。我们可以看到 $$$10$$$ 不在其中。