自动搬运

查看原文

来自洛谷，原作者为

	Hello_BABY_OvO **

搬运于2025-08-24 21:50:37，当前版本为作者最后更新于2018-04-04 10:35:29，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

先看数据范围，$n$是$10^{12}$，杜教筛是$O$($n^{\frac{2}{3}}$)的，常数还巨大，所以杜教筛做不了这道题。然后再看$l$,$r$很的小，所以可以考虑枚举然后求和，题中的$qiandao(x)=x-phi(x)$，先筛出$10^{6}$中所有的质数，然后用埃氏筛的思想去算出每个质数对$[l,r]$区间里每个数的贡献，最后再特判一下大于$\sqrt{r}$的质数就OK了！！！

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#define MAXN 1000005
#define MOD 666623333
using namespace std;
long long l,r,ans,BASE;
int cnt;
bool isprime[MAXN];
long long prime[MAXN],A[MAXN],B[MAXN];
void shai()
{
    for(int i=2;i<=MAXN;i++)
    {
        if(!isprime[i]) prime[++cnt]=i;
        for(int j=2*i;j<=MAXN;j+=i)
            isprime[j]=1;
    }
}
void work()
{
	int i=1;
    while(prime[i]*prime[i]<=r)
    {
    	long long p=prime[i];
    	for(int x=(p-l%p)%p;x<=r-l;x+=p)
    	{
    		A[x]/=p,A[x]*=p-1;
    		while(B[x]%p==0)
				B[x]/=p;
		}i++;
	}
}
int main()
{
    shai();
    scanf("%lld%lld",&l,&r);BASE=l;
    for(long long i=l;i<=r;i++)
    	A[i-BASE]=i,B[i-BASE]=i;
    work();
    for(int i=0;i<=r-l;i++) 
	{
    	if(B[i]!=1) A[i]/=B[i],A[i]*=(B[i]-1);
		ans=(ans+i+BASE-A[i])%MOD;
	}
	printf("%lld",ans);
    return 0;
}