Empty sum is zero. https://en.m.wikipedia.org/wiki/Empty_sum Also https://en.m.wikipedia.org/wiki/Vacuous_truth

I think it is O(Nlog(N)) because of the harmonic series.

I can't prove it, but here's what I did.

Assume we can use only multiplication and division. Then we can use a simple O(N²) DP to pre-process and solve each test case in O(1).

We can optimize it to roughly O(N log N) if we notice that to do the multiplication, we only need to check the divisors of a number. Also, we don't need to check all possible candidates for addition. It suffices to check for less than 10 candidates, from 1 to N. Just try adding X and N-X for each X in {1, 2, 3, 4, 5, 6, 7, 8, 9}. It's pretty intuitive if you think about it. As because you also have multiplication, you don't need to do many additions.

How to handle division and subtraction? We can't do DP naively with them, because we'll run into cycles. There are some other tricks you can use here, but the following works pretty nicely.

Assume we won't ever need to use numbers greater than 4N in our expressions. Do the previous DP with additions and multiplications for all the numbers not exceeding 4N. Then do another DP with subtraction and division (same as in before, just in reverse). After this, do we have the optimal answer? Well only for some values, but not for all because we did the DP in a fixed order and it's not necessary for them to maintain this ordering in the expressions.

What we can do though, is run this whole cycle over and over again until it converges. Each time, some new values will get updated and we can basically repeat this until all the DP values from 1 to N stops updating. This converges pretty fast, requires less than 10 iterations.

How did we get these magic numbers like 4N and 10? Just intuition and some trial and error.

#include <bits/stdtr1c++.h>

#define MAX 800000

using namespace std;

int dp[MAX];
vector<int> divisors[MAX];

void init(){
    dp[0] = dp[1] = 2, dp[2] = 1;
    for (int n = 3; n < MAX; n++) dp[n] = 2 * n;

    for (int i = 2; i < MAX; i++){
        for (int j = i + i; j < MAX; j += i){
            divisors[j].push_back(i);
        }
    }
}

void gen(){
    int n, k, l;

    for (n = 3; n < MAX; n++){
        for (k = 1; (n - k) >= 1 && k < 10; k++){
            dp[n] = min(dp[n], dp[k] + dp[n - k]);
        }
    }

    for (n = 3; n < MAX; n++){
        for (auto d: divisors[n]){
            dp[n] = min(dp[n], dp[d] + dp[n / d]);
        }
    }

    for (n = MAX - 1; n >= 3; n--){
        for (k = 1; (n + k) < MAX && k < 10; k++){
            dp[n] = min(dp[n], dp[k] + dp[n + k]);
        }
    }

    for (n = MAX - 1; n >= 3; n--){
        for (k = 2; k < 10 && n * k < MAX; k++){
            for (l = 0; l < k && (n * k + l) < MAX; l++){
                dp[n] = min(dp[n], dp[n * k + l] + dp[k]);
            }
        }
    }
}

int main(){
    freopen("two.in", "r", stdin);

    init();
    int t, n;
    for (int i = 0; i < 8; i++) gen();

    scanf("%d", &t);
    while (t--){
        scanf("%d", &n);
        printf("%d\n", dp[n]);
    }
    return 0;
}