每天一道 CodeForces 构造/思维题 难度1500 （day3）

1题目

题目链接 Factorials and Powers of Two

题目大意：

给你一个整数n(1<=n<=1e12)，它可以由两种类型的数组成

• 类型1：2的整数次幂
• 类型2：k的阶乘

这个数可以由这两种类型任意多个组成，但是组成n的数字中不能由相同数字。

问最少由多少个这两种类型的数组成整数n

2思路

这是一个整数划分问题，但是这个整数特别大，所以不能用动态规划来求。

我们可以假设只有类型1组成整数n，那么只需要n的2进制有多少个1就是答案了。

但是我们现在是两种类型的结合

假设有k个数的阶乘和为sum之后，那么就剩下n-sum了，剩下全部由类型1组成。

所以 n = k + n-k ，cnt = k + get_bit_count(n-sum)

所以为了使cnt最小，我们只需要计算所有k的可能性即可，这里k最多有14，因为15！> 1e12 了。所以我们可以用位运算来枚举所有的集合，而且集合中每个数字都不一样，还有n-sum中的所有数也不会一样。

注意这里使没办法贪心的，没有规律可言，所以只能按照枚举所以的情况即可。

3代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, int> PII;
#define x first
#define y second
const int N = 2e4 + 10;
PII a[N];
ll f[20];
int get_bit(ll x)
{
    int ans = 0;
    for (int i = 0; i < 60; i++)
    {
        if (x >> i & 1)
            ans++;
    }
    return ans;
}
void init()
{
    f[0] = 1;
    for (int i = 1; i <= 14; i++)
        f[i] = f[i - 1] * i;
    for (int i = 0; i < 1 << 14; i++)
    {
        ll ans = 0;
        int cnt = 0;
        for (int j = 0; j < 14; j++)
        {
            if (i >> j & 1)
            {
                ans += f[j + 1];
                cnt++;
            }
        }
        a[i] = {ans, cnt};
    }
}
void solve()
{
    ll n;
    cin >> n;
    int ans = 1e9;
    for (int i = 0; i < 1 << 14; i++)
    {
        if (a[i].x <= n)
        {
            ans = min(ans, a[i].y + get_bit(n - a[i].x));
        }
    }
    cout << ans << endl;
    return;
}
signed main()
{
    // freopen("in.in", "r", stdin);
    // freopen("out.out", "w", stdout);
    init();
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}