C. Factorials and Powers of Two -二进制枚举

题面

分析

阶乘最多也就用到15层，可以通过一个15位二进制数，来表示所有情况，每一位有一也就意味着加上对应的阶乘，就可以枚举所有情况。

代码

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

ll fac[20];

void get() {
   
    fac[0] = fac[1] = 1;
    for(int i = 2; i <= 15; i ++) fac[i] = fac[i - 1] * i;
}

int sum(ll n) {
   
    int ans = 0;
    for(ll i = n; i > 0; i -= i & -i) ans ++;
    return ans;
}

void solve() {
   
    ll n;
    cin >> n;
    int ans = 1e9;
    for(int i = 0; i < (1 << 15); i ++) {
   
        ll cnt = n;
        for(int j = 0; j <= 15; j ++) {
   
            if((i >> j) & 1) cnt -= fac[j + 1];
        }
        if(cnt >= 0) {
   
            ans = min(ans, sum(cnt) + sum(i));
            //cout << cnt << ' ' << i << ' ' << sum(cnt) << endl;
        }
    }
    cout << ((ans == 1e9) ? -1 : ans) << "\n";
}

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    get();
    while(T --) {
   
        solve();
    }
}