CF1542B Plus and Multiply

题目传送门

题意

有一个集合，最开始集合中只有\(1\)，又有\(a\),\(b\)，如果集合中存在\(k\)，那么将\(ka\)和\(k+b\)加入集合

试求，\(n\)是否尊在于集合之中

思路

稍加枚举（或者瞪眼大法）可得，该集合中的任何数都可被表示为\(k=ax+by\)（\(a,b\)为非负整数）

分个类更直观一些

设已有\(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;
}