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;
}