分析

等价于判断 \(n\) 能否写成如下形式 \[ n = a^x + by \] 多乘个 \(a\) 或者多加个 \(b\) 仍然形如这样。

这就相当于 \[ n \equiv a^x \quad (\bmod b) \] 因为 \(y\) 是个未知数，可以利用这个转化同余方程。或者说，\(x \equiv y \quad (\bmod b) \iff b \mid (x-y)\)。注意这里的 \(x,y,b\) 是任意的。

这个就很简单了，枚举 \(x\)，满足 \(a^x \in [1,n]\)，判断 \(a^x \bmod b\) 是否等于 \(n \bmod b\)。

为什么只用枚举使得 \(a^x \in [1,n]\) 的 \(x\)？因为 \(a,b \in \mathbb{Z^+}\)，那么如果 \(a^x\) 大于 \(n\) 的话，就不可能了。

注意特判，当 \(a=1\) 时，等价于 \(n \equiv 1 \quad (\bmod b)\)，如果成立的话，有两种情况。第一种可以直接判断 \(n \bmod b\) 是否为 1，第二种，如果 \(b=1\)，那么 \(n\) 为任何数时都成立。其他情况都无解。

CODE

#include<bits/stdc++.h>
using namespace std;
#define ll long long
long long T, n, a, b;
void solve() {
    scanf("%lld%lld%lld",&n,&a,&b);
    if(a==1) {
        if(n%b==1||b==1) puts("Yes");
        else puts("No");
        return;
    }
    int y=n%b;
    for(ll x=1;x<=n;x*=a) {
        if(x%b==y) { puts("Yes"); return; }
    }
    puts("No");
}
int main() {
    scanf("%lld",&T);
    while(T--) solve();
}