给定正整数 \(a,b,n\),每次可以进行以下操作:
假设你最开始有一个数 \(1\),求进行若干次操作后能否把这个数变成 \(n\)。
经过若干次操作后,\(1\) 一定会变成 \(((1+p_1×b)×a^{q_1}+p_2×b)×a^{q_2}+ \cdots\) 的形式。
我们把 \(1\) 和所有的 \(b\) 拆出来,那么我们就得到了 \(p×b+a^q=n\),且 \(p,q\geq0\),枚举 \(q\) 判断是否符合要求即可。
特判掉 \(a=1\) 的情况 (因为枚举 \(q\) 会造成死循环)。
少见的正常马蜂
#include<iostream> #include<cstdio> #include<cmath> using namespace std; #define int long long inline int qread(){ int tmp=0;char buf=getchar();bool f=true; while(!isdigit(buf)){if(buf=='-')f=false;buf=getchar();} while(isdigit(buf)){tmp=tmp*10+buf-'0';buf=getchar();} return f?tmp:-tmp; } bool chk(int nw,int div,int sub){ if(div==1)return (nw-1)%sub==0; for(int i=1;i<=nw;i*=div){ if((nw-i)%(sub)==0){ return true; } } return false; } signed main(){ int t=qread(); while(t--){ int n=qread(),a=qread(),b=qread(); if(chk(n,a,b))puts("Yes"); else puts("No"); } return 0; }