A. 杰哥的最小和

题解

最多存在 $1010$ 个不同的素数： $2\times 3\times 5\times 7\times 11\times 13\times 17\times 19\times 23\times 29=64696932302\; \backslash times\; 3\; \backslash times\; 5\; \backslash times\; 7\; \backslash times\; 11\; \backslash times\; 13\; \backslash times\; 17\; \backslash times\; 19\; \backslash times\; 23\; \backslash times\; 29\; =\; 6469693230$

直接二进制枚举即可

std:

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 100 + 10;
const ll INF = 1e18;

int n, tot;
int fac[MAXN], ch[MAXN];

void solve() {
    cin >> n;
    tot = 0; ll res = INF;
    for(int i = 2; i <= n / i; i++) {
        if(n % i == 0) {
            int t = 1;
            while(n % i == 0) {
                t *= i;
                n /= i;
            }
            fac[tot++] = t;
        }
    }    
    if(n != 1) fac[tot++] = n;
    for(int s = 0; s < (1 << tot); s++) {
        ll t1 = 1, t2 = 1;
        for(int i = 0; i < tot; i++) {
            if(s >> i & 1) {
                t1 *= fac[i];
            }
            else {
                t2 *= fac[i];
            }
        }
        if(t1 + t2 < res) {
            res = t1 + t2;
        }
    }
    cout << res << "\n";
}   


int main() {
    ios::sync_with_stdio(false);
    int t; cin >> t;
    while(t--) {
        solve();
    }
    return 0;
}