一道数学题

PDAST · 2024-03-31 18:31:37 · 题解

题意

就是求 N 的阶乘的因数中有多少个有 75 个因数的数。

思路

题意是简洁明了，模拟是不可能的了，一百的阶乘光高精度都得寄，所以数学应该一目了然了，但怎么个数学法呢？质因数分解就不用说了，剩下的呢？这时，你应该想起你幼儿园小班初中就学过的求因数个数的办法,按使用方法的话，应该叫指数加一相乘法，具体看这里，求因数有 75 个数的数就行了。

Code

AC 代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int a[1001],k,t[101],v[6];
int fact(int n){
    int s=1;
    for(int i=1;i<=n;i++){
        s*=i;
    }
    return s;
}
signed main(){
    int n,s=0;
    cin>>n;
    for(int i=2;i<=n;i++){
        int tmp=i;
        for(int j=2;j<=i;j++){
            while(tmp>1&&tmp%j==0){
                a[++k]=j;
                tmp/=j;
            }
        }
        if(tmp==i){
            a[++k]=i; 
        }
    }
    sort(a+1,a+k+1);
    for(int i=1;i<=k;i++){
        t[a[i]]++;
    }
    for(int i=1;i<=100;i++){
        if(t[i]>=74)v[5]++;
        if(t[i]>=24)v[4]++;
        if(t[i]>=14)v[3]++;
        if(t[i]>=4)v[2]++;
        if(t[i]>=2)v[1]++;
    } 
    s=v[5]+v[3]*(v[2]-1)+v[4]*(v[1]-1)+(fact(v[2])/fact(v[2]-2)/fact(2))*(v[1]-2);
    cout<<s;
    return 0;
}