题意:给你n个数和一个底数k,每个数每次能减去k^i(i=0,1,2,....),每个k^i只能用一次,问是否能够将每个数变为0.
题解:我们将每个数转化为k进制,因为每个k^i只能用一次,所以我们统计每个位置上的cnt,若cnt>1，则需要多次用到k^i,则不满足条件.
代码:
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5 #include <algorithm> 6 #include <stack> 7 #include <queue> 8 #include <vector> 9 #include <map> 10 #include <set> 11 #include <unordered_set> 12 #include <unordered_map> 13 #define ll long long 14 #define fi first 15 #define se second 16 #define pb push_back 17 #define me memset 18 const int N = 1e6 + 10; 19 const int mod = 1e9 + 7; 20 using namespace std; 21 typedef pair<int,int> PII; 22 typedef pair<long,long> PLL; 23 24 int t; 25 int n,k; 26 ll a[N]; 27 int cnt[N]; 28 29 bool check(){ 30 me(cnt,0,sizeof(cnt)); 31 for(int i=0;i<n;++i){ 32 int pos=0; 33 while(a[i]){ 34 cnt[pos]+=a[i]%k; 35 a[i]/=k; 36 pos++; 37 } 38 } 39 for(int i=0;i<=60;++i){ 40 if(cnt[i]>1) return false; 41 } 42 return true; 43 } 44 45 int main() { 46 ios::sync_with_stdio(false); 47 cin>>t; 48 while(t--){ 49 cin>>n>>k; 50 for(int i=0;i<n;++i) cin>>a[i]; 51 if(check()) puts("YES"); 52 else puts("NO"); 53 } 54 55 56 57 return 0; 58 }