给定n和k,输入n个数字,每次可以让第i个数字减去k的x次幂,每个x只能用一次,问能否将全部数字变为0
首先预处理k的x次幂,需要注意的是,当出现k的x次幂大于1e16的时候再结束。然后对于每个数字,不断的减去k的次幂,如果最后不是0,那么就输出NO,否则输出YES。
#include<bits/stdc++.h>
#define x first
#define y second
#define IOS ios::sync_with_stdio(false);cin.tie(0);
using namespace std;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
typedef pair<long,long> PLL;
typedef pair<char,char> PCC;
typedef long long LL;
const int N=2*1e5+10;
const int M=150;
const int INF=0x3f3f3f3f;
const int MOD=998244353;
LL a[M],f[M];
bool st[M];
void solve(){
memset(st,0,sizeof st);
int n,k;cin>>n>>k;
f[0]=1;
int idx=0;
for(int i=1;;i++){
f[i]=f[i-1]*k;
if(f[i]>1e16){
idx=i;
break;
}
}
for(int i=0;i<n;i++) cin>>a[i];
bool zero=true;
for(int i=0;i<n;i++) if(a[i]!=0) zero=false;
if(zero) cout<<"YES"<<endl;
else{
int fg=0;
for(int i=0;i<n;i++){
for(int j=idx;j>=0;j--){
if(a[i]>=f[j]){
if(st[j]){
fg=1;
break;
}else{
a[i]-=f[j];
st[j]=true;
}
}
}
}
for(int i=0;i<n;i++) if(a[i]) fg=1;
if(fg) cout<<"NO"<<endl;
else cout<<"YES"<<endl;
}
}
int main(){
IOS;
int t;cin>>t;
while(t--) solve();
return 0;
}