题意
给定一个数 \(n\)，求 \(n!\) 的因数中，刚好有 \(75\) 个因数的数的个数。
分析
首先有这样一个性质，对于一个数 \(a\)，我们将其分解质因数，即
\[a = \prod_{i = 1}^{n} p_i^{k_i} \]那么，\(a\) 的因数个数就是
\[sum = \prod_{i = 1}^{n} (k_i+1) \]简单证明一下，对于第 \(i\) 个质因数，可以选 \([0, k_i]\) 个，所以最终能组合出来的不同因数就是 \(sum\) 个。
题干要求因数个数为 \(75\) 的因数，首先考虑什么样的数有 \(75\) 个因数——没错，我们将 \(75\) 分解因数，发现
\(75 = 5 \times 5 \times 3\)，则 $a= p_1^4 p_2^4 p_3^2 $；
同理，
\(75 = 5 \times 15\)，$a= p_1^{4} p_2^{14} $
\(75 = 25 \times 3\)，$a= p_1^{24} p_2^2 $
\(75 = 75 \times 1\)，$a= p_1^{74} $
因为 \(n!\) 的质因数包括了其所有因数的质因数，而每种质因数组合只能确定一个数，故我们可以直接考虑每种情况如何构造出 \(a\)。我们令 \(s_i\) 表示，个数大于等于 \(i\) 的质因数个数。因为多余的数没有用，所以这里我们直接考虑大于等于的数。
那么，对于第一种情况，对答案的贡献为 \(C_{s_4}^2*(s_2-2)\)；
同理，第二种的贡献 \(s_{14}*(s_{4}-1)\)；
第三种的贡献 \(s_{24}*(s_2-1)\)；
第四种的贡献 \(s_{75}\)。
最后看数据范围。 \(n\) 说小不小，\(100!\) 肯定不是直接求出来；然后 \(n\) 又说大不大，可以考虑对 \(1\) 到 \(n\) 的数分解质因数，那么 \(n!\) 的质因数分解就是对 \([1, n]\) 的数的质因数的指数做前缀和。最后的答案就是将以上四种贡献加起来。
#include<bits/stdc++.h>
using namespace std;
const int N = 305;
int n;
int a[105][105];
bool vis[105];
int pr[105], tot;
void init(){
for(int i = 2; i<=100; i++){
if(vis[i]) continue;
vis[i] = 1, pr[++tot] = i;
for(int j = i; j<=100; j+=i){
vis[j] = 1;
}
}//数据范围很小很小所以简单筛一下质数就行。
for(int i = 2; i<=100; i++){
int tmp = i;
for(int j = 1; j<=tot; j++){
if(tmp%pr[j] == 0){
while(tmp%pr[j] == 0){
tmp/=pr[j];
a[i][j]++;//对1~100内的数分解质因数。
}
}
}
}
}
int f[N];
int sum[N];
int ts[N];
int main(){
scanf("%d", &n);
init();
for(int i = 1; i<=n; i++){
for(int j = 1; j<=tot; j++){
sum[j]+=a[i][j];//求n!因数分解后质因数的指数。
}
}
int ans = 0;
int L = 0, R = 0, Y = 0;
sort(sum+1, sum+1+tot, greater<int>());
for(int i = 1; i<=tot; i++){
if(sum[i]>=24){
ts[24]++;
}
if(sum[i]>=14){
ts[14]++;
}
if(sum[i]>=74){
ts[74]++;
}
if(sum[i]>=4){
ts[4]++;
}
if(sum[i]>=2){
ts[2]++;
}
}
if(ts[74]){
ans+=ts[74];
}
if(ts[24]){
ans+=ts[24]*(ts[2]-1);
}
if(ts[14]){
ans+=(ts[14]*(ts[4]-1));
}
if(ts[4]){
ans+=(ts[4]*(ts[4]-1)/2*(ts[2]-2));
}
printf("%d\n", ans);
return 0;
}