自动搬运

查看原文

来自洛谷，原作者为

	Lyx8058 模拟赛

搬运于2025-08-24 23:14:10，当前版本为作者最后更新于2025-08-19 17:36:02，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

思路：

不难发现我们可以将 $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;
}