题目描述

Description

Input

Output

Sample Input

2

Sample Output

3

HINT

题目分析

先%一发题面
考虑丢番图那题
将$n!$看成$n$就是原题了
因为$(n!)^2$过大 瓶颈在于不能直接求出$(n!)^2$的约数个数
先把问题化简：求$(n!)$的约数个数
因为：$(n!)=a_1^{p_1}\times a_2^{p_2}\times \cdots\times a_k^{p_k}$
所以：$(n!)^2=a_1^{2p_1}\times a_2^{2p_2}\times \cdots\times a_k^{2p_k}$
所以：$(n!)^2$约数和个数为$((2p_1+1)\times(2p_2+1)\times\cdots\times(2p_k+1))$
然后我们来求$pi$
又因为$(n!)$里的所有质因子都是$1\sim n$以内的素数
所以先快筛素数，再对于$ai$枚举$n$以内的它的所有的倍数，然后暴力求出$1 \sim n$的所有数中，一共含有$ai$ 的幂次$pi$是多少。
然后乘一起就是答案

#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int n;
long long ans=1;
int prime[2000000],v[2000000];
void work()
{
    for(int i=2;i<=1000005;i++)
    {
        if(v[i]==0) prime[++prime[0]]=i;
        for(int j=1;j<=prime[0]&&i*prime[j]<=1000005;j++)
        {
            v[i*prime[j]]=1;
            if(i%prime[j]==0) break;
        }
    }
}
int c[5000000];
int main()
{
    scanf("%d",&n);
    work();
    for(int i=1;i<=prime[0];i++)
        for(int j=prime[i];j<=n;j+=prime[i])
            for(int k=j;k%prime[i]==0;k/=prime[i]) c[i]++;
    for(int i=1;i<=prime[0];i++) ans=ans*(c[i]<<1|1),ans%=1000000007;
    printf("%lld",ans);
    return 0;
}