自动搬运

查看原文

来自洛谷，原作者为

	qwaszx 不再为往事受困.

搬运于2025-08-24 21:51:15，当前版本为作者最后更新于2019-04-19 11:26:46，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

这题好毒瘤啊...果然是zzq...

首先要去切了这道题来学会区间筛积性函数

然后你发现这题$r\leq 10^{18}$....处理$\sqrt{r}$个素数是行不通的.

但是我们注意一点，$\mu$函数可以认为是只和素数的个数有关的，所以我们只拿$10^6$个数去筛.假设$i$已经除去了所有$1e6$以下的质因子，那么$i$只有三种情况:

$\begin{cases}i=pq\\i=p\\i=p^2\end{cases}(p,q\in prime,p\neq q)$

对于第一种情况，多了两个质因子，$\mu$不变；对于第二种情况$\mu$取负；对于第三种情况$\mu=0$.

如何去判断呢?$i=p^2$只需要判断$\left\lfloor\sqrt{i}\right\rfloor^2=i$；$i=p$需要使用$Miller-Rabin$素性测试；剩下的就是$i=pq$的情况了.

$Miller-Rabin$的时候因为模数是$long\ long$的所以需要特殊处理乘法

首先龟速乘根本跑不动(快速幂+龟速乘是两个$\log$的)，所以

long long mul(long long a,long long b,long long m)
{
	return (a*b-(long long)((long double)a/m*b)*m+m)%m;
}

原理baidu吧QAQ

这里因为数据水而使用了简化版的$Miller-Rabin$(只测$2$和$3$，不二次探测)

注释中有正常的$Miller-Rabin$

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
long long fac[2000000],l,r;
int mu[2000000],prime[2000000],p[2000005],cnt;
long long sqr(long long x){return x*x;}
void make(int n)//打表1e6的素数
{
	p[0]=p[1]=1;
	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 mul(long long a,long long b,long long m)
{
	return (a*b-(long long)((long double)a/m*b)*m+m)%m;
}
long long qpower(long long a,long long b,long long m)
{
	long long ans=1;
	for(;b;b>>=1,a=mul(a,a,m))if(b&1)ans=mul(ans,a,m);
	return ans;
}
/*
bool Miller_Rabin(long long x,long long p)//真的MillerRabin，底下要选取12个素数 
{
	long long pd=qpower(p,x-1,x),s=x^1;
	while(pd==1&&!(s&1))s>>=1,pd=qpower(p,s,x);
	return pd==1||pd==(x^1);
}
*/
bool Miller_Rabin(long long x,long long p){return qpower(p,x-1,x)==1;}
bool judge(long long n)
{
	for(int i=1;i<=2;i++)if(!Miller_Rabin(n,prime[i]))return 0;
	return 1;
}
int main()
{
	scanf("%lld%lld",&l,&r);
	for(long long i=l;i<=r;i++)fac[i-l]=i,mu[i-l]=1;
	make(1000000);
	for(int i=1;i<=cnt&&prime[i]<=r;i++)
	{
		int t=prime[i];
		for(long long j=((l-1)/t+1)*t;j<=r;j+=t)
		{
			int k=0;
			while(fac[j-l]%t==0)++k,fac[j-l]/=t;
			if(k>1)mu[j-l]=0;else mu[j-l]=-mu[j-l];//区间筛
		}
	}
	long long ans=0;
	for(long long i=l;i<=r;i++)
	{	
		if(fac[i-l]!=1)
		{
			long long t=fac[i-l];
			if(sqr((long long)sqrt(t))==t)mu[i-l]=0;
			else if(judge(t))mu[i-l]=-mu[i-l];//多一个质因子
		}
		ans+=mu[i-l];
	}
	cout<<ans<<endl;
}

同理大概也可以筛$\sigma$...毒瘤...