自动搬运

查看原文

来自洛谷，原作者为

	qwaszx 不再为往事受困.

搬运于2025-08-24 22:02:05，当前版本为作者最后更新于2019-07-01 12:28:58，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

答案就是$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);
	}
}

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