CF1542B Plus and Multiply
题目传送门
题意
有一个集合，最开始集合中只有\(1\)，又有\(a\),\(b\)，如果集合中存在\(k\)，那么将\(ka\)和\(k+b\)加入集合
试求，\(n\)是否存在于集合之中
思路
稍加枚举（或者瞪眼大法）可得，该集合中的任何数都可被表示为\(k=ax+by\)（\(x,y\)为非负整数）
分个类更直观一些
设已有\(k\)为\(ax+by\)，则会有新的两个数\(ak\)和\(b+k\)进入集合，一次求出：
-
\(ak=a(xa)+b(ya)\)
-
\(b+k=ax+b(y+1)\)
所以最后只需要枚举\(x\)，再看\(n-ax\)是否整除\(b\)（即是否存在非负整数\(y\)）即可
代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,a,b,now;
void run()
{cin>>n>>a>>b;if(a==1){if(n%b==1 || n==1 || b==1) cout<<"Yes"<<endl;else cout<<"No"<<endl;return;}now=1;while(now<=n){if((n-now)%b==0){cout<<"Yes"<<endl;return;}now*=a;}cout<<"No"<<endl;
}
signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t;cin>>t;while(t--) run();system("pause");return 0;
}
