题解 P3601 【签到题】

Hello_BABY_OvO · 2018-04-04 10:35:29 · 题解

先看数据范围，n是10^{12}，杜教筛是O(n^{\frac{2}{3}})的，常数还巨大，所以杜教筛做不了这道题。然后再看l,r很的小，所以可以考虑枚举然后求和，题中的qiandao(x)=x-phi(x)，先筛出10^{6}中所有的质数，然后用埃氏筛的思想去算出每个质数对[l,r]区间里每个数的贡献，最后再特判一下大于\sqrt{r}的质数就OK了！！！

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#define MAXN 1000005
#define MOD 666623333
using namespace std;
long long l,r,ans,BASE;
int cnt;
bool isprime[MAXN];
long long prime[MAXN],A[MAXN],B[MAXN];
void shai()
{
    for(int i=2;i<=MAXN;i++)
    {
        if(!isprime[i]) prime[++cnt]=i;
        for(int j=2*i;j<=MAXN;j+=i)
            isprime[j]=1;
    }
}
void work()
{
    int i=1;
    while(prime[i]*prime[i]<=r)
    {
        long long p=prime[i];
        for(int x=(p-l%p)%p;x<=r-l;x+=p)
        {
            A[x]/=p,A[x]*=p-1;
            while(B[x]%p==0)
                B[x]/=p;
        }i++;
    }
}
int main()
{
    shai();
    scanf("%lld%lld",&l,&r);BASE=l;
    for(long long i=l;i<=r;i++)
        A[i-BASE]=i,B[i-BASE]=i;
    work();
    for(int i=0;i<=r-l;i++) 
    {
        if(B[i]!=1) A[i]/=B[i],A[i]*=(B[i]-1);
        ans=(ans+i+BASE-A[i])%MOD;
    }
    printf("%lld",ans);
    return 0;
}