P3601 签到题

思路

注意到求的qiandao(x)就是\(x-\phi(x)\)

但是\(l,r\le 10^{12}\)，所以不能直接杜教筛

但是\(r-l\le 10^{6}\)，所以可以先筛出1e6（\(\sqrt{10^{12}}\)）内的素数，再用这些素数更新l~r的phi，最后特殊处理大于1e6的素因子（只有一个）

代码

#include <cstdio>

#include <cstring>

#include <algorithm>

#define int long long

using namespace std;

const int MOD = 666623333;

int cnt,iprime[1001000],isprime[1001000],numA[1001000],phix[1001000];

int l,r,ans=0;

void prime(int n){

    isprime[1]=true;

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

        if(!isprime[i])

            iprime[++cnt]=i;

        for(int j=1;j<=cnt&&iprime[j]*i<=n;j++){

            isprime[iprime[j]*i]=true;

            if(i%iprime[j]==0)

                break;

        }

    }

}

void phi(void){

    for(int i=1;i<=cnt&&iprime[i]*iprime[i]<=r;i++){

        int t=l/iprime[i];

        if(l%iprime[i])

            t++;

        for(int j=t;j*iprime[i]<=r;j++){

            phix[j*iprime[i]-l]=phix[j*iprime[i]-l]/(iprime[i])*(iprime[i]-1);

            while(numA[j*iprime[i]-l]%iprime[i]==0)

                numA[j*iprime[i]-l]/=iprime[i];

        }

    }

    for(int i=l;i<=r;i++)

        if(numA[i-l]>1)

            phix[i-l]=phix[i-l]/numA[i-l]*(numA[i-l]-1);

}

signed main(){

    prime(1000100);

    scanf("%lld %lld",&l,&r);

    for(int i=l;i<=r;i++){

        numA[i-l]=i;

        phix[i-l]=i;

    }

    phi();

    for(int i=l;i<=r;i++){

        ans=(ans+(i-phix[i-l])%MOD+MOD)%MOD;

    }

    printf("%lld\n",ans);

    return 0;

}