Codefroces C.Adding Powers

Description

给出n个数和数字k，问这n个数是不是每个都：

等于k的某些幂次之和

这些幂次彼此各不相同

Analyze

将每个数字拆解成k的幂次之和的形式

        long long a, cnt[60];
        memset(cnt, 0, sizeof(cnt));
        for(int i = 0; i < n; ++i)
        {
            cin >> a;
            int idx = 0;
            while(a > 0)
            {
                cnt[idx++] += a % k;
                a /= k;
            }
        }

就是上面这段代码，智慧结晶啊！

运用了逐次降幂的思想（让我想起了Java老师讲进制转换）

举例：k的x次幂，拿他 /= k，可以完成 x 次，之后成为 1，运用上面的代码得到cnt[x] == 1。同理，若是k的x次幂与k的y次幂之和，这个数字跑完代码后得到cnt[x] == 1 && cnt[y] == 1 && cnt[others] == 0。

算法很清楚地显示了这个数字在 k的幂次 这一角度的组成。

对于这一题，针对所有数字，使用同一个cnt数组，若是所有的1都落在不同位上，则YES，若是落在同一位上则NO！

这想法真好。

Code

#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;


int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        int n, k;
        cin >> n >> k;

        long long a, cnt[60];
        memset(cnt, 0, sizeof(cnt));
        for(int i = 0; i < n; ++i)
        {
            cin >> a;
            int idx = 0;
            while(a > 0)
            {
                cnt[idx++] += a % k;
                a /= k;
            }
        }

        bool ok = true;
        for (int i = 0; i < 60; ++i)
            if (cnt[i] > 1)
                ok = false;
        cout << (ok ? "YES" : "NO") << "\n";
    }
    return 0;
}