杜教筛

https://www.luogu.org/problemnew/show/P4213

#include<bits/stdc++.h>
#include<tr1/unordered_map>
#define fi first
#define se second
#define INF 0x3f3f3f3f
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define pqueue priority_queue
#define NEW(a,b) memset(a,b,sizeof(a))
#define lowbit(x) (x&(-x))
#define si(x) scanf("%d",&x)
#define sl(x) scanf("%lld",&x)
#define lc (d<<1)
#define rc (d<<1|1)
const double pi=4.0*atan(1.0);
const double e=exp(1.0);
const int maxn=6e6+8;
typedef long long LL;
typedef unsigned long long ULL;
const LL mod=1e6+3;
const ULL base=1e7+7;
using namespace std;
bool vis[maxn];
int mu[maxn],sum1[maxn],phi[maxn];
LL sum2[maxn];
int cnt,prim[maxn];
tr1::unordered_map<LL,LL>w1;
tr1::unordered_map<int,int>w;
void get(int N){
    phi[1]=mu[1]=1;
    for(int i=2;i<=N;i++){
        if(!vis[i]){
            prim[++cnt]=i;
            mu[i]=-1;phi[i]=i-1;
        }
        for(int j=1;j<=cnt&&prim[j]*i<=N;j++){
            vis[i*prim[j]]=1;
            if(i%prim[j]==0){
                phi[i*prim[j]]=phi[i]*prim[j];
                break;
            }
            else mu[i*prim[j]]=-mu[i],phi[i*prim[j]]=phi[i]*(prim[j]-1);
        }
    }
    for(int i=1;i<=N;i++)sum1[i]=sum1[i-1]+mu[i],sum2[i]=sum2[i-1]+phi[i];
}
int djsmu(int x){
    if(x<=6000000)return sum1[x];
    if(w.count(x))return w[x];
    int ans=1;
    for(int l=2,r;l<=x;l=r+1){
        r=x/(x/l);
        ans-=(r-l+1)*djsmu(x/l);
    }
    return w[x]=ans;
}
LL djsphi(LL x){
    if(x<=6000000)return sum2[x];
    if(w1.count(x))return w1[x];
    LL ans=x*(x+1)/2;
    for(LL l=2,r;l<=x;l=r+1){
        r=x/(x/l);
        ans-=(r-l+1)*djsphi(x/l);
    }
    return w1[x]=ans;
}
int main(){
    cin.tie(0);
    cout.tie(0);
    int T;
    cin>>T;
    get(6000000);
    int x;
    while(T--){
        scanf("%d",&x);
        printf("%lld %d
",djsphi(x),djsmu(x));
    }
}

http://www.51nod.com/Challenge/Problem.html#problemId=1244

#include<bits/stdc++.h>
#include<tr1/unordered_map>
#define fi first
#define se second
#define INF 0x3f3f3f3f
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define pqueue priority_queue
#define NEW(a,b) memset(a,b,sizeof(a))
#define lowbit(x) (x&(-x))
#define si(x) scanf("%d",&x)
#define sl(x) scanf("%lld",&x)
#define lc (d<<1)
#define rc (d<<1|1)
const double pi=4.0*atan(1.0);
const double e=exp(1.0);
const int maxn=6e6+8;
typedef long long LL;
typedef unsigned long long ULL;
const LL mod=1e6+3;
const ULL base=1e7+7;
using namespace std;
bool vis[maxn];
int mu[maxn],sum1[maxn];
int cnt,prim[maxn];
tr1::unordered_map<LL,LL>w;
void get(int N){
    mu[1]=1;
    for(int i=2;i<=N;i++){
        if(!vis[i]){
            prim[++cnt]=i;
            mu[i]=-1;
        }
        for(int j=1;j<=cnt&&prim[j]*i<=N;j++){
            vis[i*prim[j]]=1;
            if(i%prim[j]==0){
                break;
            }
            else mu[i*prim[j]]=-mu[i];
        }
    }
    for(int i=1;i<=N;i++)sum1[i]=sum1[i-1]+mu[i];
}
LL Sum(LL x) {
    return x <= 6000000 ? sum1[x] : w[x];
}
void DJ_shai(LL n) {
    for(LL i = n, y; i >= 1; i = n / (y + 1)) {
        y = n / i;
        if (y <= 6000000) continue;
        LL ret = 0;
        for (LL j = 2, l, pre = 1; j <= y; ++j) {
            l = y / j;
            j = y / l;
            ret += Sum(l) * (j - pre);
            pre = j;
        }
        w[y]=1ll-ret;
    }
}
int main(){
    get(6000000);
    LL x,y;
    scanf("%lld%lld",&x,&y);
    DJ_shai(y);
    DJ_shai(x-1);
    printf("%lld",Sum(y)-Sum(x-1));
}