CompetitiveProgramming/codeforces/100325/D.cpp at master · phonglnDEV/CompetitiveProgramming · GitHub

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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112

#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a),_b=(b); i<=_b; ++i)
#define FORD(i,a,b) for(int i=(a),_b=(b); i>=_b; --i)
#define REP(i,a) for(int i=0,_a=(a); i < _a; ++i)

#define DEBUG(X) { cout << #X << " = " << X << endl; }
#define PR(A,n)  { cout << #A << " = "; FOR(_,1,n) cout << A[_] << ' '; cout << endl; }
#define PR0(A,n) { cout << #A << " = "; REP(_,n) cout << A[_] << ' '; cout << endl; }

#define sqr(x) ((x) * (x))
#define ll long long
#define SZ(x) ((int) (x).size())
using namespace std;

const int MN = 40111;
ll primes[MN], nPrime;
int sieve[MN];

void init() {
    FOR(i,2,1000) if (!sieve[i]) {
        int j = i*i;
        while (j < MN) {
            sieve[j] = i;
            j += i;
        }
    }
    FOR(i,2,MN-1) if (!sieve[i]) primes[++nPrime] = i;
//    DEBUG(nPrime);
//    PR(primes, 10);
}

ll f[33][33][33][33];

ll res[30] = {
1,
8,
30,
108,
338,
1042,
2997,
8405,
22651,
59520,
151957,
379692,
927621,
2224234,
5236585,
12130779,
27669592,
62229989,
138095695,
302673028,
655627974,
1404599866,
2977831388,
6251060784,
12999299704,
26791990051
};

int main() {
    ios :: sync_with_stdio(0); cin.tie(0);
    freopen("false.in", "r", stdin);
    freopen("false.out", "w", stdout);
    init();
    ll n;
/*
    FOR(k,1,26) {
        memset(f, 0, sizeof f);
        f[0][0][0][0] = 1;
        FOR(u,0,k) FOR(v,0,k)
            FOR(lastu,0,u) FOR(lastv,0,v) {
                ll cur = f[u][v][lastu][lastv];
                if (!cur) continue;

                FOR(nextu,0,k-u)
                    FOR(nextv,0,k-v)
                    if (make_pair(nextu, nextv) >= make_pair(lastu, lastv)) {
                        f[u + nextu][v + nextv][nextu][nextv] += cur;
                    }
            }

        ll res = 0;
        FOR(u,0,k) FOR(v,0,k)
            res += f[k][k][u][v];
        cout << res - 1 << endl;
    }
    */
    while (cin >> n) {
        // find k
        int k = 1;
        FOR(i,1,nPrime) {
            int p = primes[i];
            if (n % p == 0) {
                int cur = 0;
                while (n % p == 0) {
                    ++cur;
                    n /= p;
                }
                k = cur;
                break;
            }
        }
//        DEBUG(k);

        // # non-trivial factorization
        cout << res[k-1] << endl;
    }
}