发布时间：2024-07-31

区间筛思想

题意：
$ f(x)表示小于等于x且与x不互质的数，即x- \phi (x) $
$ 1 \leq l \leq r \leq 10^{12} ,r-l \leq 10^6 $
思路：

大于 $ \sqrt r $ 的质因数只有一个，因此先把小于等于的质因数筛出来，算贡献
大于的特判即可
$ O(1e6+(1e6)log(1e6)) $

cpp

vector<int> prime;
bool vis[N];
void sieve(){
    for(int i=2;i<N;i++){
        if(!vis[i]){
            vis[i]=1;
            prime.push_back(i);
        }
        for(int j=0;j<prime.size()&&prime[j]*i<N;j++){
            vis[i*prime[j]]=1;
            if(i%prime[j]==0)break;
        }
    }
}
int phi[N],val[N],l,r;
void work(){
    for(auto &p:prime){
        for(int i=(l+p-1)/p*p;i<=r;i+=p){
            phi[i-l]/=p;
            phi[i-l]*=p-1;
            while(val[i-l]%p==0)val[i-l]/=p;
        }
    }
}
void solve(){
    cin>>l>>r;
    sieve();
    for(int i=l;i<=r;i++)val[i-l]=phi[i-l]=i;
    work();
    int ans=0;
    for(int i=l;i<=r;i++){
        if(val[i-l]>1)phi[i-l]/=val[i-l],phi[i-l]*=val[i-l]-1;// 特判大质因子
        (ans+=i-phi[i-l])%=mod;
    }
    cout<<ans<<"\n";
}

区间筛思想 ​

区间筛思想