CF Div2 729 Plus and Multiply

原题链接：Problem - 1542B - Codeforces

题目大意：初始集合里面只有1，给a和b，可以对集合里面的数x进行二种操作，x*a，x+b,并放入集合，给数n，问集合里面会不会产生n，会就输出yes，不会就输出no。

思路：如果n会出现在集合里面，那么他一定是由a^c1+c2*b这种形式，c1和c2为未知数，如果进行操作1，那么就会对数进行乘a的操作，因为初始只有1，那么必定会产生a^c1这种数，如果进行了操作2，那么就会加上b，如果继续操作2，那么就会变成2b，如果操作1，那么就会变成ab，但是肯定可以提出一个公因子b，然后将另一部分看为c2。因为c1是操作1的操作数，而且2^64>1e16，所以可以直接从小到大枚举c1。

//冷静，冷静，冷静
//调不出来就重构 
#pragma GCC optimize(2)
#pragma GCC optimize("O3")
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
typedef long double ld; 
typedef pair<ll,ll> pii;
const int N=1e6+10,mod=998244353;
int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);ll t;cin>>t;while(t--){ll n,a,b;cin>>n>>a>>b;ll now=1,f=0;if(a==1) {if((n-1)%b==0){cout<<"Yes"<<endl;}else cout<<"No"<<endl;continue;}while(now<=n){if((n-now)%b==0)//如果a^c1已经减完了，那么剩下的数是b的倍数{f=1;break;}now*=a;//a^c1}if(f)cout<<"Yes"<<endl;else cout<<"No"<<endl;}return 0;
}