首页 > 代码库 > BZOJ 2721 樱花

BZOJ 2721 樱花

问题转化为求(n!)^2有多少个约数。

#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#define maxn 1005000#define mod 1000000007using namespace std;long long n,cnt[maxn],a[maxn];void es_shaker(){    for (long long i=1;i<=n;i++)    {        if (a[i]!=1)        {            for (long long j=1;j*i<=n;j++)            {                while (!(a[j*i]%i))                    a[j*i]/=i,cnt[i]++;            }        }    }}int main(){    scanf("%lld",&n);    for (long long i=1;i<=n;i++) a[i]=i;    es_shaker();    long long ans=1;    for (long long i=1;i<=n;i++)        ans=(ans*(2*cnt[i]+1))%mod;    printf("%lld\n",ans);    return 0;}

 

BZOJ 2721 樱花