Plus and Multiply
题意翻译
有一个无穷大的正整数集合 $S$,该集合按下面所述方法生成:
- 数字 $1$ 在集合 $S$ 中。
- 若数字 $x$ 在该集合中,那么数 $x \times a$ 和数 $x+b$ 均在集合 $S$ 中。(其中 $a$ 与 $b$ 为给定常数)
现在给出数 $n,a,b$,请判断 $n$ 是否在集合 $S$ 中(此处给出的 $a$ 与 $b$ 就是上述集合生成方法中的 $a$ 和 $b$),若在请输出 `Yes`,否则输出 `No`。多组数据。
令数据组数为 $t$,那么有 $1 \leq t \leq 10^5$,$1 \leq n,a,b \leq 10^9$。
题目描述
There is an infinite set generated as follows:
- $ 1 $ is in this set.
- If $ x $ is in this set, $ x \cdot a $ and $ x+b $ both are in this set.
For example, when $ a=3 $ and $ b=6 $ , the five smallest elements of the set are:
- $ 1 $ ,
- $ 3 $ ( $ 1 $ is in this set, so $ 1\cdot a=3 $ is in this set),
- $ 7 $ ( $ 1 $ is in this set, so $ 1+b=7 $ is in this set),
- $ 9 $ ( $ 3 $ is in this set, so $ 3\cdot a=9 $ is in this set),
- $ 13 $ ( $ 7 $ is in this set, so $ 7+b=13 $ is in this set).
Given positive integers $ a $ , $ b $ , $ n $ , determine if $ n $ is in this set.
输入输出格式
输入格式
The input consists of multiple test cases. The first line contains an integer $ t $ ( $ 1\leq t\leq 10^5 $ ) — the number of test cases. The description of the test cases follows.
The only line describing each test case contains three integers $ n $ , $ a $ , $ b $ ( $ 1\leq n,a,b\leq 10^9 $ ) separated by a single space.
输出格式
For each test case, print "Yes" if $ n $ is in this set, and "No" otherwise. You can print each letter in any case.
输入输出样例
输入样例 #1
5
24 3 5
10 3 6
2345 1 4
19260817 394 485
19260817 233 264
输出样例 #1
Yes
No
Yes
No
Yes
说明
In the first test case, $ 24 $ is generated as follows:
- $ 1 $ is in this set, so $ 3 $ and $ 6 $ are in this set;
- $ 3 $ is in this set, so $ 9 $ and $ 8 $ are in this set;
- $ 8 $ is in this set, so $ 24 $ and $ 13 $ are in this set.
Thus we can see $ 24 $ is in this set.
The five smallest elements of the set in the second test case is described in statements. We can see that $ 10 $ isn't among them.