[C++知识库]Codeforces Round #774 (Div. 2) C. Factorials and Powers of Two

x为powerful数即：x是2^k或者x是k!（阶乘）
给定一个数n，问n最少可以由几个powerful数组成。
n的范围最大是10¹²

考虑使用二进制，n最大10¹²，15！就已经超过10¹²，所以只需要求到14!，所以是阶乘的powerful数只有14个，那么可以枚举这14个数，每个数选或者不选，计和为sum，那么令n-sum = x，x的二进制中的每个1都可以用2^k来表示，那么就几个1就有几个powerful数，再加上我们总共用了几个阶乘powerful数。

本题一定有解。

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

LL kk[16];
int bit[45];

int ones(LL x)
{
    int cnt = 0;
    for(int i = 39; i >= 0; i --)
    {
        if(x >> i & 1) cnt ++;
    }
    return cnt;
}

int main()
{
    int t; cin >> t;
    LL temp = 1;
    for(int i = 0; i < 14; i ++)
    {
        temp *= (i+1);
        kk[i] = temp;
    }
    while(t --)
    {
        int res = 0x3f3f3f3f;
        LL n; cin >> n;
        for(int i = 39; i >= 0; i --)
        {
            bit[i] = (n >> i) & 1;            
        }
        for(int i = 0; i < 1 << 14; i ++)
        {
            int x = i;
            LL sum = 0;
            for(int j = 0; j < 14; j ++)
            {
                if(x >> j & 1 == 1)
                {
                    sum += kk[j];
                }
            }
            if(sum > n) continue;
            res = min(res, ones(n-sum) + ones(x));
        }
        cout << res << endl;
    }
    return 0;
}