Участник:Rimon/Divisors of factorial

Материал из DISCOPAL
Перейти к: навигация, поиск

https://www.spoj.com/problems/DIVFACT/

C++ (gcc 8.3)

#include<cstdio>
#define ll long long
const int ntf=1e9+7;
ll sum[50003];
int tmp[50003];
inline ll qpw(ll x,ll v)
{
    ll r=1;
    while(v)
    {
        (v&1)&&(r=r*x%ntf),x=x*x%ntf,v>>=1;
    }
    return r;
}
int t,n;
int main()
{
    sum[0]=1;
    for(int i=1;i<=5e4;++i)
    {
        sum[i]=sum[i-1];
        int t=i;
        for(int j=2;j*j<=t;++j)
        {
            if(t%j)continue;
            int cnt=0;
            while(t%j==0)++cnt,t/=j;
            sum[i]=sum[i]*qpw(tmp[j]+1,ntf-2)%ntf;
            sum[i]=sum[i]*((tmp[j]+=cnt)+1)%ntf;
        }
        if(t>1)
        {
            sum[i]=sum[i]*qpw(tmp[t]+1,ntf-2)%ntf;
            sum[i]=sum[i]*((++tmp[t])+1)%ntf;
        }
    }
    scanf(" %d",&t);
    while(t--)
    {
        scanf(" %d",&n);
        printf("%lld\n",sum[n]);
    }
    return 0;
}