Adding Powers
time limit per test2 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output
Suppose you are performing the following algorithm. There is an array v1,v2,…,vn filled with zeroes at start. The following operation is applied to the array several times — at i-th step (0-indexed) you can:
either choose position pos (1≤pos≤n) and increase vpos by ki;
or not choose any position and skip this step.
You can choose how the algorithm would behave on each step and when to stop it. The question is: can you make array v equal to the given array a (vj=aj for each j) after some step?
Input
The first line contains one integer T (1≤T≤1000) — the number of test cases. Next 2T lines contain test cases — two lines per test case.
The first line of each test case contains two integers n and k (1≤n≤30, 2≤k≤100) — the size of arrays v and a and value k used in the algorithm.
The second line contains n integers a1,a2,…,an (0≤ai≤1016) — the array you’d like to achieve.
Output
For each test case print YES (case insensitive) if you can achieve the array a after some step or NO (case insensitive) otherwise.
Example
inputCopy
5
4 100
0 0 0 0
1 2
1
3 4
1 4 1
3 2
0 1 3
3 9
0 59049 810
outputCopy
YES
YES
NO
NO
YES
Note
In the first test case, you can stop the algorithm before the 0-th step, or don’t choose any position several times and stop the algorithm.
In the second test case, you can add k0 to v1 and stop the algorithm.
In the third test case, you can’t make two 1 in the array v.
In the fifth test case, you can skip 90 and 91, then add 92 and 93 to v3, skip 94 and finally, add 95 to v2.
感谢我方数论选手为我助力~传送门
题意： 给你n个数和k，问这n个数是否能够由不重复的k的次幂本身或和构成。
思路：
我们来考虑一下什么时候不符合题意，当有一个k的次幂被用了多次时，不符合题意。所以可以联想到进制转换（我进制转换没学好没联想到qwq）
我们把一个数拆成k进制，k的次幂前面的系数要么是0，要么是1，如果系数为1的这一位在之前已经被使用过，就说明不符合题意
再来解释一下这个地方~
其实这个是进制转换有关的东西~可以先理解一下k=2的情况，比如n=5时，用二进制表示就是101，当该位为1时说明2的次幂要用到。而这个101就是通过5不断对2取余得到的
代码：
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=110; int a[maxn],n,k; int main(){ int t;cin>>t; while(t--){ cin>>n>>k; memset(a,0,sizeof a); bool flag=1; ll tmp=0,cnt=0; for(int i=1;i<=n;i++){ cin>>tmp;cnt=0; while(tmp){ a[cnt]+=tmp%k; tmp/=k; if(a[cnt]>=2) flag=0; cnt++; } } if(flag) puts("YES"); else puts("NO"); } return 0; }
康康代码：
#include<iostream> #include<stdio.h> #include<string.h> #include<algorithm> #include<math.h> #include<queue> #include<stack> #include<map> using namespace std; const int inf =0x3f3f3f3f; const int maxn=1e5+5; const int mod =1000; #define PI 3.14159265358979323846 #define ll long long #define ull unsigned ll #define DB double inline int read() { int x=0,f=1;char s=getchar(); while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();} while(s<='9'&&s>='0'){x=x*10+s-'0';s=getchar();} return x*f; } ll a[maxn],p[maxn]; ll f(ll a,ll b)//a转b { ll i=0; while(a) { p[i]=a%b; a/=b; i++; } return i; } map<ll,ll >mp; int main() { int T; cin>>T; ll n,k,ans,flag=1,t; while(T--) { flag=1; scanf("%lld %lld",&n,&k); for(int i=1;i<=n;i++) { t=-1; scanf("%lld",&a[i]); if(a[i]==0) continue; ans=f(a[i],k); for(int i=0;i<ans;i++) { //t++; if(p[i]==1&&mp[i]==1) { flag=0; break; } if(p[i]==1) mp[i]=1; else if(p[i]>1) { flag=0; break; } } } if(flag) cout<<"YES"<<endl; else cout<<"NO"<<endl; mp.clear(); } }
没有看到超级月亮，只有深夜掉分场~
但是真的快乐哈哈哈
