题解 | #2^20#

首先我们要知道这题不存在无解情况（子弹是无限的）

然后根据题目的2^20考虑到二进制

举个例子先：

5 = 101

10 = 5 * 2 = 1010

不难发现当一个数乘以2之后，相当于在这个数的二进制末尾添加了一个0

而能被2^20整除的条件就是这个数拆分成二进制后，第一个1出现在第20位之前

所以答案必然在20以内（就算第一位是1，最差情况这个数乘以20次2后也能被2^20整除）

然后讨论特例，比如7 = 111，我们可以发现7 + 1 = 8 = 1000，如果我们直接让7乘以20次2明显比7 + 1再乘以17次2次数更多

所以我们可以枚举n + 0到n + 20的所有情况进行比较，找出最小的操作次数

下面是我的代码，写的很答辩凑合看看吧（跑

#include <bits/stdc++.h>

using i64 = long long;
#define int long long

void solve(){
    int n, ans = 1e18;//ans = 20是一样的，不影响
    std::cin >> n;

    if(n >= (1ll << 20)){
        if(n % (1ll << 20) == 0){
            std::cout << 0 << '\n';
            return;
        }else{
            n %= (1ll << 20);
            for(int i = 0; i <= 20; ++i){
                int tt = n + i, cnt = 0;
                while(tt % 2 == 0){
                    tt /= 2;
                    cnt++;
                }
                ans = std::min({20 - cnt + i, (1ll << 20) - n, ans});
            }
        }
    }else{
        for(int i = 0; i <= 20; ++i){
            int tt = n + i, cnt = 0;
            while(tt % 2 == 0){
                tt /= 2;
                cnt++;
            }
            ans = std::min({ans, 20 - cnt + i, (1ll << 20) - n});
        }
    }

    std::cout << ans << '\n';
}
signed main() {

    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr), std::cout.tie(nullptr);

    i64 _ = 1;
    std::cin >> _;

    while (_--) {
        solve();
    }

    return 0;
}