AtCoder题解｜ABC 114D 756

题目信息 📚

【题目描述】

You are given an integer $N$. Among the divisors of $N!$ ($=1 \times 2 \times \ldots \times N$), how many Shichi-Go numbers are there?

Here, a Shichi-Go number is a positive integer that has exactly 75 divisors.

When a positive integer $A$ divides a positive integer $B$, $A$ is said to be a divisor of $B$. For example, $6$ has four divisors: $1, 2, 3$, and $6$.

【输入】

Input is given from Standard Input in the following format:

$N$

【输出】

Print the number of the Shichi-Go numbers that are divisors of $N!$.

【数据范围】

$1 \leq N \leq 100$
$N$ is an integer.

【输入样例1】

【输出样例1】

There are no Shichi-Go numbers among the divisors of $9! = 1 \times 2 \times \ldots \times 9 = 362880$.

【输入样例2】

【输出样例2】

There is one Shichi-Go number among the divisors of $10! = 3628800$: $32400$.

【输入样例3】

【输出样例3】

【题目来源】

https://atcoder.jp/contests/abc114/tasks/abc114_d

题目解析 🍉

【题目分析】

本题考察数论中的算数基本定理与质因数分解。

算术基本定理/唯一分解定理：当 $n >= 2$ 且 $n$ 为整数时，$n = p_1^{a_1} \times p_2 ^ {a_2} \times \ldots \times p_k^{a_k}$，$p_1,p_2,\ldots,p_k$ 均为质数。

$n$ 共有 $(a_1 + 1) \times (a_2 + 1) \times \ldots \times (a_k + 1)$ 个 divisors（即选若干个或不选 $p_1$，选若干个或不选 $p_2$，… ，选若干个或不选 $p_k$。全选即得到 $n$，全不选得到 $1$）

有了以上基础，我们就可以将题目中的 $N!$ 进行质因数分解，统计每个质因子出现次数。

若想构成 75 个divisors 的数，则必须为：

$3 * 5 * 5 = 75$ → $p_1^{2} * p_2^{4} * p_3^{4}$
$3 * 25 = 75$ → $p_1^{2} * p_2^{24}$
$5 * 15 = 75$ → $p_1^{4} * p_2^{14}$
$1 * 75 = 75$ → $p_1^{74}$

因此只需分别统计以上四类情况即可。

【C++代码】

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;
int n;
map<int, int> mp;
vector<int> v;

// 对x进行质因数分解，并将结果存入map中
void prime_factorization(int x) {
    for (int i = 2; i <= x / i; i++) {
        while (x % i == 0) {
            mp[i]++;
            x /= i;
        }
    }
    if (x > 1) mp[x]++;
}

// 在vecotr中搜索有几个数满足v[i]>=x
int s(int x) {
    int cnt = 0;
    for (int i = 0; i < v.size(); i++) {
        if (x <= v[i]) cnt++;
    }
    return cnt;
}

int main() {
    cin >> n;

    // 对n!进行质因数分解
    for (int i = 1; i <= n; i++) prime_factorization(i);

    // 将质因子出现的次数放入vector中进行排序
    for (auto t: mp) v.push_back(t.second);
    sort(v.begin(), v.end());

    // 对75进行分解
    // 75 = 75 = 3 * 25 = 5 * 15 = 3 * 5 * 5
    // 即拥有75个divisors的数x，可以分解为：x = a1^74 / x = a1^2 * a2^24 / x = a1^4 * a2^14 / x = a1^2 * a2^4 * a3^4
    int cnt = 0;
    cnt += s(74);
    cnt += s(24) * (s(2) - 1);
    cnt += s(14) * (s(4) - 1);
    cnt += s(4) * (s(4) - 1) / 2 * (s(2) - 2);
    cout << cnt << endl;

    return 0;
}