BZOJ-2721: [Violet 5]樱花

Description

求正整数解的个数（mod 10^9+7）。n<=10^6

和上一题一样，转化：(x-n!)*(y-n!)=(n!)^2
那么就是求n!的所有质因子的指数。
快筛一遍质数，一顿除就好了。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
int n,pri[501000],cnt;
bool v[1001000];
const ll mod=1000000007;
ll fna=1;
void quick_prime()
{
    for(int j,i=2;i<=n;++i)
    {
        if(!v[i]) pri[++cnt]=i;
        for(j=1;i*pri[j]<=n&&j<=cnt;++j)
        {
            v[i*pri[j]]=1;
            if(i%pri[j]==0) break; 
        }
    }
}
ll work(ll x,ll y)
{
    ll re=0;
    while(x) x/=y,re+=x;
    return re;
}
int main()
{
    scanf("%d",&n); quick_prime();
    for(int i=1;i<=cnt;++i)
        fna=(work(n,pri[i])*2%mod*fna%mod+fna)%mod;
    printf("%lld",fna);
    return 0;
}