Codeforces Round #729 (Div. 2) B. Plus and Multiply (数论/暴力)

https://codeforces.com/contest/1542/problem/B

题目大意：

有一个无限集合生成如下:

1在这个集合中。

如果x在这个集合中，x⋅a和x+b都在这个集合中。

给定n a b，问我们n在不在这个集合中？

input 
5
24 3 5
10 3 6
2345 1 4
19260817 394 485
19260817 233 264
output 
Yes
No
Yes
No
Yes

我一开始想的就是a^?+b*?==n
但是用23 3 5这组数据把自己hack掉了哈哈哈，真是呆b一个啊

• 莫得怂，直接冲就完了

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PII;
const LL MAXN=1e18;
const LL N=1000200,M=2002;
bool check(LL n,LL a,LL b,LL num)
{
    while(num<=n)
    {
        if((n-num)%b==0) return true;//是否可以直接用b来凑
        if(a==1) return false;//b都凑不到了，而且a竟然还是没用的1
        num*=a;
    }
    return false;
}
int main()
{
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
    LL T=1;
    cin>>T;
    while(T--)
    {
        LL n,a,b;
        cin>>n>>a>>b;
        bool flag=check(n,a,b,1);
        if(flag==true) cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
    return 0;
}

原文地址：http://www.cnblogs.com/Vivian-0918/p/16826430.html