526互联

Asia Dhaka Regional Contest C (阶乘分解)

发布时间 2023-05-05 14:33:31作者: 陌上&初安

原题点这

前置知识点：

题意：

给出 \(n\)，问 \(n!\) 的因子的因子的个数和。

思路：

学会上面的阶乘分解之后，我们能一眼看出来这道题也一定跟它有关系，所以我们按照惯例先对\(n!\) 进行质因数分解。

n! = \({p_1}^{a_1}\times\) \({p_2}^{a_2}\)\(\times\) \({p_3}^{a_3}\)\(\times\) ... \(\times\) \({p_k}^{a_k}\)

我们单独考虑每一中质数，我们假设一个素数为 \(p\)，它的幂次为 \(a\) ，因为我们要求的是因子的因子个数，而且它一共有幂次 \(a\) ，那么该因子的因子就有 \(0,1,2 ...a\) 的 \(a + 1\) 种选择。
即\(p^{0},p^{1},p^{2},,,,p^{a}\)
对于\(p^0\)，因子个数为1，对于\(p^1\)，因子个数为2，对于\(p^a\)，因子个数为\(a+1\)。所以总的因子个数就为：\(1+2+3+...+a+(a+1) = \dfrac{(a+1)(a+2)}{2}\) （等差数列求和）

而对于每一个素数的贡献都如上，所以总贡献为：\(\prod_{i=1}^{k}\dfrac{(a_i+1)(a_i+2)}{2}\)。

AC代码：

#include <bits/stdc++.h>
#include <unordered_map>
#include <unordered_set>
#define xx first
#define yy second
#define IOS ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(0);
#define fixed fixed<<setprecision
#define endl '\n'
#define int long long

using namespace std;

const int mod = 1e7 + 7;
const int N2 = 1e6 + 10;

int cntt, primes[N2], n;
bool stt[N2];
// 线性筛质数
void initpr(int n)
{ 
    for(int i = 2; i <= n; i ++)
    { 
        if(!stt[i]) primes[cntt ++] = i;
        for(int j = 0; primes[j] * i <= n; j ++)
        {
            stt[primes[j] * i] = true;
            if(i % primes[j] == 0) break;
        }
    } 
}
// 阶乘分解
int f(int x)
{
    int res = 0, tt = n;
    while(tt)
    {
        res += tt / x;
        tt /= x;
    }
    return res;
}

void solve()
{
    while(cin >> n && n)
    {
        int res = 1;
        for(int i = 0; i < cntt && primes[i] <= n; i ++)
        {
            int num = f(primes[i]);
            res = (res * (num + 1) * (num + 2) / 2) % mod;
        }
        cout << res << endl;
    }
}

signed main()
{
    IOS
    initpr(N2);
    int T = 1;
    //cin >> T;
    while(T --)
    {
        solve();
    }
    
    return 0;
}