Adding Powers

题目连接: Adding Powers

题目:

见链接

大致题意:

给你一个数字k 和一个整型数组, 问你能否用一个或多个kⁱ的值(和), 来表示整个数组里的各个数字, 其中要求i不能重复使用.
例如: 给定数字9, 数组为: 1, 82;
1 = 9⁰, 82 = 9⁰ + 9², 即使我们表达出了整个数组, 但是 i=0 被用了两次, 因此是不成立的.

解题思路:

这其实就是一个进制转换, 但是要求从十进制转换到k进制后, 各个数位上的数字只能为0或者1.
当我们把一个数字i进行转换时:
如果当前取余的结果不是0或者1, 说明无解.
如果是1, 那么看当前的i是否已经被使用即可.
如果为0则无需判断.

AC代码:

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
int n, k; bool num[100];
bool spilt(ll x, int k) {
	int cou = 0;
	while (x) {
		int temp = x % k; x /= k;
		if (temp > 1) return 0;
		if (temp && num[cou]) return 0;
		if (temp) num[cou] = 1;
		cou++;
	}
	return 1;
}

int main(void)
{
	int t; cin >> t;
	while (t--) {
		memset(num, 0, sizeof(num));
		scanf("%d %d", &n, &k);
		ll x; bool flag = 1;
		for (int i = 1; i <= n; ++i) {
			scanf("%lld", &x);
			if (flag) flag = spilt(x, k); 
		}
		if (flag) cout << "YES" << endl;
		else cout << "NO" << endl;
	}
	return 0;
}

END