luogu P3601 签到题

链接P3601 签到题

• 求$$\sum_{i=l}^{r} i-\phi_i$$
• \(l,r\leq 10^{12},\ r-l\leq 10^6\)
• 杜教筛似乎做不了。
• 然后再看\(l\)，\(r\)的差很小，所以可以考虑枚举然后求和。
• 先筛出\(10^6\)中所有的质数，那么对于区间内每一个数，最多只会存在一个大于\(10^6\)的质数。
• 所以枚举每一个质数，算出这一个质数对区间内的\(\phi\)所贡献，最后再特判一下大于\(10^6\)即可。
• 复杂度为\(O(\sqrt r*logr+(r-l)*logr)\)。

#include<bits/stdc++.h>

#define R register int

#define ll long long

using namespace std;

const int mod=666623333;

const int N=1600001;

ll l,r,A[N],B[N];

int n,ans,tot,Mark[N],prm[N];

int main(){

	cin>>l>>r,n=sqrt(r);

	for(R i=2;i<=n;++i){

		if(!Mark[i])prm[++tot]=i;

		for(R j=1;j<=tot&&prm[j]*i<=n;++j){

			Mark[i*prm[j]]=1;

			if(i%prm[j]==0)break;

		}

	}

	for(R i=0;i<=r-l;++i)A[i]=B[i]=i+l;

	for(R j=1;j<=tot&&1ll*prm[j]*prm[j]<=r;++j){

		ll le=prm[j]*(l/prm[j]),ri=prm[j]*(r/prm[j]);

		for(ll i=le;i<=ri;i+=prm[j])

			if(i>=l){

				R pos=i-l;

				B[pos]=B[pos]/prm[j]*(prm[j]-1);

				while(A[pos]%prm[j]==0)A[pos]/=prm[j];

			}

	}

	for(R i=0;i<=r-l;++i){

		if(A[i]>1)B[i]=B[i]/A[i]*(A[i]-1);

		ans=(ans+(l+i-B[i])%mod)%mod;

	}

	cout<<ans<<endl;

    return 0;

}