题解 P4626 【一道水题 II】

· · 题解

这范围明摆着分块打表啊...

答案就是lcm(1,2,\cdots,n)

考虑lcm的意义，对于一个质因子p，那么它对答案的贡献是p^a，其中a是1到n中每个数最多含质因子p的个数.于是可以筛出所有质数然后再求出贡献，这可以简单地求出：

long long solve(int p)
{
    long long ans=p;
    while(ans*p<=n)ans=ans*p;
    return ans;
}

然后再注意到如果p>\sqrt{n}那么它对答案的贡献就是p，所以我们可以按1e6分块打表出每一块内素数的积以及块的前缀积(去掉第一块，这一块可能贡献指数不是1).然后对于整块直接查表，非整块区间筛出所有素数.

复杂度O(1e6).

打表程序

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=1e8,mod=1e8+7;
const int blo=1e6;
int w[5000],prime[N],cnt;
bool p[N+5];
void make()
{
    for(int i=1;i<=100;i++)w[i]=1;
    for(int i=2;i<=N;i++)
    {
        int id=(i-1)/blo+1;
        if(!p[i])prime[++cnt]=i,w[id]=1ll*w[id]*i%mod;
        for(int j=1;j<=cnt&&i*prime[j]<=N;j++)
        {
            p[i*prime[j]]=1;
            if(i%prime[j]==0)break;
        }
    }
    w[1]=1;for(int i=3;i<=100;i++)w[i]=1ll*w[i]*w[i-1]%mod;
}
int main()
{
    freopen("data.txt","w",stdout);
    make();
    for(int i=1;i<=100;i++)printf("%d,",w[i]);
}

提交程序

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int blo=1e6,N=5e6,mod=1e8+7;
const int W[500]={0,1,4279041,78522927,97275812,6626498,90103459,19755829,89404363,31420837,78259116,79495350,63384896,76365496,77671792,60888616,14364168,69179499,73237343,47511561,98202707,9638787,8923490,19377161,14025453,83914297,99211028,91698985,11861010,41728948,85011248,2957451,96835040,13279739,65389333,35674577,69539515,43558531,90167843,65612508,96727630,84411969,10432978,81144826,76822534,44673268,48780356,42026053,71419640,925833,75468296,56122076,11730540,24214526,57670707,87561236,60795551,16258057,38969193,93135220,99449198,86687779,48716439,54282180,9747238,6014664,88132693,90624798,78394444,54259153,2424434,71634841,6763549,80339105,74090298,10910559,39590831,57807866,78084208,54389248,4052287,74604335,99190428,89368783,73470487,32097770,29222100,30538785,3048397,89311543,48798411,36895907,88691881,24323948,4724247,97882710,84490696,93965490,66087028,92642640,55440368};
int prime[N],p[N],n,cnt;
void make(int n)
{
    for(int i=2;i<=n;i++)
    {
        if(!p[i])prime[++cnt]=i;
        for(int j=1;j<=cnt&&i*prime[j]<=n;j++)
        {
            p[i*prime[j]]=1;
            if(i%prime[j]==0)break;
        }
    }
}
long long solve(int p)
{
    long long ans=p;
    while(ans*p<=n)ans=ans*p;
    return ans;
}
int main()
{
    scanf("%d",&n);
    if(n<=blo)
    {
        make(n);int ans=1;
        for(int i=1;i<=cnt;i++)
            ans=solve(prime[i])*ans%mod;
        printf("%d\n",ans);
    }
    else
    {
        make(blo);int ans=1;
        for(int i=1;i<=cnt;i++)
            ans=solve(prime[i])*ans%mod;
        int id=(n-1)/blo;ans=1ll*ans*W[id]%mod;
        long long L=id*blo+1,R=n;for(int i=0;i<=R-L;i++)p[i]=0;
        for(int i=1;i<=cnt&&prime[i]*prime[i]<=R;i++)//区间筛
        {
            int l=L/prime[i]*prime[i];if(l<L)l+=prime[i];
            while(l<=R)p[l-L]=1,l+=prime[i];
        }
        int tmp=0;
        for(int i=L;i<=R;i++)
            if(!p[i-L])++tmp,ans=1ll*ans*i%mod;
        printf("%d\n",ans);
    }
}

比第二快了二十多倍吧(雾