原题点这
前置知识点:
- 阶乘分解 可看这篇博客
题意:
给出 \(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;
}
标签:Dhaka,Contest,个数,times,因子,阶乘,include,define
From: https://www.cnblogs.com/liqs2526/p/17374077.html