参考 y总详细的讲解 ,自己比葫芦画瓢也推导了一波,自我感觉这是一道比较不错的题目,写此题解纪念一下吧。
先总结一下解决该问题所需要的前备知识: 分解质因数 + 约数个数 + 素数筛 + 阶乘分解
基础 + 基础 = 提高
加油,打工人!!!
解题思路在下图中展示:
C++ AC代码:
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int mod = 1e9+7;
typedef long long ll;
const int N = 1000010;
int prime[N],cnt;
bool vis[N];
void get_prime(int n)
{
for(int i = 2;i <= n;i++)
{
if(!vis[i]) prime[cnt++] = i;
for(int j = 0;prime[j] <= n / i;j++)
{
vis[prime[j] * i] = true;
if(i % prime[j] == 0) break;
}
}
}
int main()
{
int n; scanf("%d",&n);
get_prime(n);
ll res = 1;
for(int i = 0;i < cnt;i++)
{
int p = prime[i];
int cnt = 0;
for(int j = n;j >= 1;j /= p) cnt += j / p;
res = res * (2 * cnt + 1) % mod;
}
cout << res;
return 0;
}
注意:这道题最终是求的是$n!^2$的质因数分解的结果,在 $n!$ 的质因数分解的基础之上将各个质因子的指数分别乘以 $2$ 即可得。