题解：P12267 [蓝桥杯 2024 国 Python B] 儿童数

· · 题解

思路：

不难发现我们可以将 2024! 分解成形如 p_1^{a_1}\times p_2^{a_2}\times ...\times p_m^{a_m}，其中，p_1 到 p_m 均是质数。

那么若要满足 2024! 是 n^{61} 的倍数，则须满足 n^{61} 分解成 p_1^{b_1}\times p_2^{b_2}\times ...\times p_m^{b_m} 的时候满足 \forall 1\leq i\leq m，a_i\geq b_i。

那么问题就转化为在 2024! 的质因数里面任意选择若干个数所组成的数有多少个（算上 1）。

我们可以知道，分解成以上形式时，可以得到公式为 \prod_{i=1}^{m} (a_i+1)，那么由于要得到的数字为 n^{61} 中的 n，我们根据乘法原理得到 \prod_{i=1}^{m} (\lfloor \frac{a_i}{61} \rfloor+1)。

那么本题也是比较轻松的做完了。

代码：

说明：该代码已经过格式化，放心观看。

#include<bits/stdc++.h>

#define int long long
using namespace std;
const int N = 2024;
int p[N], cnt = 0, dis[N]; //2024
bool check(int x) {
    for (int i = 2; i <= sqrt(x); i++) {
        if (x % i == 0) return false;
    }
    return true;
}
void solve(int x) {
    int j = 1;
    while (x > 1 && j <= cnt) {
        while (x % p[j] == 0 && x > 1) {
            x /= p[j];
            dis[p[j]]++;
        }
        j++;
    }
    dis[x]++;
    return;
}
signed main() {
    for (int i = 2; i <= 2024; i++) {
        if (check(i)) {
            p[++cnt] = i;
            dis[i]++;
        } else solve(i);
    }
    int ans = 1;
    for (int i = 1; i <= cnt; i++) {
        ans *= (1 + dis[p[i]] / 61);
    }
    cout << ans << "\n";
    return 0;
}