题目可以转化为 $n$ 是否可以写成 $ax+yb$ 的形式。
证明:若 $ax+yb$ 乘上了 $a$,结果为 $a^{x+1}+(ay)b$,仍然是这个形式。加上了 $b$ 同理。
而 $n=ax+yb$ 可以转化为 $n\equiv ax\pmod{b}$ 且 $n\ge a_x$。
枚举 $x$ 计算即可。$x$ 为指数,增长很快不会超时。
另外这题需要注意一些值为 $1$ 的细节。
#include<iostream>
#include<map>
#define int long long
using namespace std;
int a[205];
signed main()
{
int T;
cin>>T;
while(T--)
{
int n,a,b;
cin>>n>>a>>b;
if(a==1)
{
if(n%b==1||n==1||b==1) cout<<"Yes\n";
else cout<<"No\n";
continue;
}
int k=n%b;
bool flg=0;
for(int i=1;i<=n;i*=a)
if(i%b==k) flg=1;
if(flg) cout<<"Yes\n";
else cout<<"No\n";
}
return 0;
}