CF1542B

Aryper · 2021-11-15 10:16:22 · 个人记录

Plus and Multiply

这个数集的特点可以通过手动扩展的方式看出，当然，也可以通过直接分析性质看出。

首先，对于 b，我们只有加法操作，所以 b 的次数只能为 1，但系数未知。

我们分析一手 b 的系数，发现它应该可以表示成一个关于 a 的任意非负整系数多项式，换句话说，这是一个 a 进制数，可以表示所有的非负系数。

而 a 呢？我们发现集合中的数只能包含一个只关于 a 的项，因为 a 无法在数集中作加法。所以 a 的次数是一个任意数。

因此，我们发现一个数在数集中，当且仅当它可以表示为 a^{k_1}+k_2b（k_1,k_2\in N）。

那么怎么判断呢？O(1) 的方法不太好想，我们可以尝试稍微弱一些的方法。

显然这个 a^{k_1} 增长很快，我们可以枚举 k_1，再判断剩下的数是否能被 b 整除，然后就彳亍了。

当然需要特判一手 a=1。

时间复杂度 O(T\log_an)。

代码：

#include<iostream>
#include<cstdio>
#include<queue>
#include<algorithm>
#include<cstring>
#define ll long long
using namespace std;

ll T,n,a,b,flg,tmp;

inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9') {ret=(ret<<3)+(ret<<1)+ch-'0';ch=getchar();}
    return ret*f;
}

void write(ll x) {
    static char buf[22];static ll len=-1;
    if(x>=0) {
        do{buf[++len]=x%10+48;x/=10;}while(x);
    }
    else {
        putchar('-');
        do{buf[++len]=-(x%10)+48;x/=10;}while(x);
    }
    while(len>=0) putchar(buf[len--]);
}

void writeln(ll x) {
    write(x);putchar('\n');
}

int main() {

    T=read();

    while(T--) {
        flg=0;
        n=read();a=read();b=read();
        tmp=1;
        if(a==1) {
            if((n-a)%b==0) flg=1;
        }
        else
        while(tmp<=n) {
            if((n-tmp)%b==0) {
                flg=1;break;
            }
            tmp*=a;
        }
        if(flg) printf("Yes\n");
        else printf("No\n");
    }

    return 0;
}