According to \(\lfloor\frac{a}{bc}\rfloor=\lfloor\frac{\lfloor\frac{a}{b}\rfloor}{c}\rfloor\) , we can implement the following code (using dfs):

#include <iostream>
using namespace std;
long long n;
int p, num = 0, prime[26];
inline void init() {
    static int mark[110];

    for (int i = 2; i <= p; i++) {
        if (!mark[i]) {
            prime[num++] = i;
        }

        for (int j = 0, t = 2; j < num
                && i * t <= p; t = prime[++j]) {
            mark[i * t] = 1;

            if (i % t == 0) {
                break;
            }
        }
    }
}
unsigned int ans = 0;
void dfs(long long n, int p) {
    if (!p) {
        ans += __lg(n) + 1;
        return;
    }

    dfs(n, p - 1);

    if (n >= prime[p]) {
        dfs(n / prime[p], p);
    }
}
int main() {
    cin >> n >> p;
    init(), dfs(n, num - 1);
    cout << ans << endl;
    return 0;
}

Notes: The code specifically deals with \(p=2\) . And the answer at this point is \(\lfloor\log_2 n\rfloor+1\) .

But this code needs to run for about 7s at the limit data. Think about how we can optimize it?

Memorization search! Of course, if the value range is very large, it will run very slowly. So we only record the answers when the value range is relative small (e.g. \(2^{16}\) ).

#include <iostream>
using namespace std;
long long n;
int p, num = 0, prime[26];
inline void init() {
    static int mark[110];

    for (int i = 2; i <= p; i++) {
        if (!mark[i]) {
            prime[num++] = i;
        }

        for (int j = 0, t = 2; j < num
                && i * t <= p; t = prime[++j]) {
            mark[i * t] = 1;

            if (i % t == 0) {
                break;
            }
        }
    }
}
const int N = 1 << 16;
unsigned int ans = 0, f[25][N];
void dfs(long long n, int p) {
    if (n < N && f[p][n]) {
        ans += f[p][n];
        return;
    }

    if (!p) {
        ans += __lg(n) + 1;
        return;
    }

    unsigned int Ans = ans;
    dfs(n, p - 1);

    if (n >= prime[p]) {
        dfs(n / prime[p], p);
    }

    if (n < N) {
        f[p][n] = ans - Ans;
    }
}
int main() {
    cin >> n >> p;
    init(), dfs(n, num - 1);
    cout << ans << endl;
    return 0;
}

This code is fully sufficient to pass the question, it only needs to run for about 250ms.

But you can also reduce the constant by changing the memorization search to preprocessing dp. (It only needs to run for about 160ms.)

#include <iostream>
using namespace std;
long long n;
int p, num = 0, prime[26];
const int N = 1 << 18;
unsigned int ans = 0, f[25][N];
inline void init() {
    static int mark[110];

    for (int i = 2; i <= p; i++) {
        if (!mark[i]) {
            prime[num++] = i;
        }

        for (int j = 0, t = 2; j < num
                && i * t <= p; t = prime[++j]) {
            mark[i * t] = 1;

            if (i % t == 0) {
                break;
            }
        }
    }

    for (int i = 1; i < N; i++) {
        f[0][i] = __lg(i) + 1;
    }

    for (int i = 1; i < num; i++) {
        for (int t = prime[i], j = 0; j < N; j += t) {
            unsigned int V = f[i][j / t];

            for (int k = j; k < N && k < j + t; k++) {
                f[i][k] = V + f[i - 1][k];
            }
        }
    }
}
void dfs(long long n, int p) {
    if (n < N) {
        ans += f[p][n];
        return;
    }

    if (!p) {
        ans += __lg(n) + 1;
        return;
    }

    dfs(n, p - 1);

    if (n >= prime[p]) {
        dfs(n / prime[p], p);
    }
}
int main() {
    cin >> n >> p;
    init(), dfs(n, num - 1);
    cout << ans << endl;
    return 0;
}