C. Factorials and Powers of Two

题目：C. Factorials and Powers of Two

题意：

        若一个数是2的次方，或是某个数的阶乘，则这个数为powerful数，给出一个数n，求n最少可表示为多少个powerful数的和

        数据范围：。

思路：

        1、任意一个数肯定可以表示成若干个2的次方数的和，因为把这个数转化成二进制形式，为1的位置就是一个2的次方数。

        2、用阶乘来替换掉一些1，15的阶乘已经超过，所以共0~14个阶乘，二进制枚举选或不选，假如选了cnt个阶乘，和为sum，剩下的用2的次方数来表示，则这种选法的答案就是cnt 加上 (n-sum)的二进制表示中1的个数。

        3、__builtin_popcountll()函数可求一个数的二进制表示有多少个1

代码：

#include <iostream>
#include <algorithm>using namespace std;typedef long long LL;
LL fac[15];void init()
{LL num = 1;fac[0] = 1;for(int i = 1; i <= 14; i++)fac[i] = fac[i-1] * i;
}int main()
{init();int t;cin >> t;while(t--){LL n;cin >> n;int res = 0x3f3f3f3f;for(int i = 0; i <= (2<<14); i++){LL tmp = n;int cnt = 0;for(int j = 0; j <= 14; j++)if((i>>j) & 1){tmp -= fac[j];cnt++;}res = min(res, cnt + __builtin_popcountll(tmp));}cout << res << endl;}return 0;
}