1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include <cstdio>
#include <tuple>
#include <string>
typedef unsigned I;
typedef std::tuple<I, I> P;
typedef std::string S;
using std::get;

static const I CS = 60000000;
static I cache[CS] = {0,};

static I get(I x);

static P ilo(I x) {
        P best = P{x, 0};
        if (x < 5)
                return best;
        for (I v=2; v*v<=x; ++v) {
                if ((x%v) == 0) {
                        I val = get(v) + get(x/v);
                        if (val < get<0>(best)) {
                                best = P{val, v};
                        }
                }
        }
        return best;
}

static I get(I x) {
        if (x < 5)
                return x;
        if (x < CS && cache[x])
                return cache[x];
        P p0 = ilo(x);
        P p1 = ilo(x-1);
        P p2 = ilo(x-2);

        I v0 = get<0>(p0);
        I v1 = 1 + get<0>(p1);
        I v2 = 2 + get<0>(p2);
        I vbest = std::min(std::min(v0, v1), v2);

        if (x < CS)
                cache[x] = vbest;
        return vbest;
}

static S gets(I x) {
        if (x == 1) {
                return "1";
        }
        if (x == 2) {
                return "(1+1)";
        }
        P p0 = ilo(x);
        P p1 = ilo(x-1);
        P p2 = ilo(x-2);

        I v0 = get<0>(p0);
        I v1 = 1 + get<0>(p1);
        I v2 = 2 + get<0>(p2);
        I vbest = std::min(std::min(v0, v1), v2);
        if (vbest > 100)
                return "NIE";

        if (vbest == v0) {
                I il = get<1>(p0);
                if (il == 0) {
                        return "(1+" + gets(x-1) + ")";
                } else {
                        return gets(il) + "*" + gets(x/il);
                }
        } else if (vbest == v1) {
                return "(1+" + gets(x-1) + ")";
        } else {
                return "(1+1+" + gets(x-2) + ")";
        }
}

int main() {
        I t, k;
        scanf("%u\n", &t);
        for (I i=0; i<t; ++i) {
                scanf("%u\n", &k);
                printf("%s\n", gets(k).c_str());
        }
        return 0;
}