CF1542B Plus and Multiply

有一个无限集合，其生成方式如下： - $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"。输出时字母大小写均可。

在第一个测试用例中，$24$ 的生成过程如下： - $1$ 在集合中，所以 $3$ 和 $6$ 也在集合中； - $3$ 在集合中，所以 $9$ 和 $8$ 也在集合中； - $8$ 在集合中，所以 $24$ 和 $13$ 也在集合中。 因此可以看出 $24$ 在该集合中。 第二个测试用例中，该集合最小的五个元素已在题目描述中给出，可以看出 $10$ 不在其中。 由 ChatGPT 4.1 翻译