A 洛谷 P3601 签到题 [欧拉函数 质因子分解]

题目背景

这是一道签到题！

建议做题之前仔细阅读数据范围！

题目描述

我们定义一个函数：qiandao(x)为小于等于x的数中与x不互质的数的个数。

这题作为签到题，给出l和r，要求求。

输入输出格式

输入格式：

一行两个整数，l、r。

输出格式：

一行一个整数表示答案。

输入输出样例

输入样例#1：

233 2333

输出样例#1：

1056499

输入样例#2：

2333333333 2333666666

输出样例#2：

153096296

说明

对于30%的数据，。

对于60%的数据，。

对于100%的数据，，。

---

比赛时傻逼了一直想用lp[]进行质因子分解可是空间不够

其实只要筛出sqrt(r)范围的质数就可以了

不能对每个数直接质因子分解 根号会T

所以用了管用伎俩 每个质数枚举[l,r]范围的倍数进行质因子分解 复杂度O(n~nlogn)

//

//  main.cpp

//  AA

//

//  Created by Candy on 2017/2/2.

//  Copyright © 2017年 Candy. All rights reserved.

//

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

using namespace std;

typedef long long ll;

const int N=1e6+,MOD=;

inline ll read(){

    char c=getchar();ll x=,f=;

    while(c<''||c>''){if(c=='-')f=-; c=getchar();}

    while(c>=''&&c<=''){x=x*+c-''; c=getchar();}

    return x*f;

}

ll l,r;

bool notp[N];

int p[N];

void sieve(int n){//printf("%d\n",n);

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

        if(!notp[i]) p[++p[]]=i;

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

            notp[i*p[j]]=;

            if(i%p[j]==) break;

        }

    }

}

ll phi[N],x[N];

void solve(){

    for(int i=;i<=r-l+;i++) x[i]=phi[i]=i+l-;

    for(int i=;i<=p[];i++){

        ll lb=p[i]*(l/p[i]),rb=p[i]*(r/p[i]);//printf("hi %d %d %d %d\n",i,p[i],lb,rb);

        for(ll j=lb;j<=rb;j+=p[i]) if(j>=l){

            phi[j-l+]=phi[j-l+]/p[i]*(p[i]-);

            while(x[j-l+]%p[i]==) x[j-l+]/=p[i];

        }

    }

    for(int i=;i<=r-l+;i++) if(x[i]>) phi[i]=phi[i]/x[i]*(x[i]-);

    //for(int i=1;i<=r-l+1;i++) printf("phi %d %lld\n",i+l-1,phi[i]);

}

ll ans;

int main(int argc, const char * argv[]){

    l=read();r=read();

    sieve(sqrt(r)+);

    solve();

    for(ll i=;i<=r-l+;i++) (ans+=i+l--phi[i])%=MOD;

    printf("%lld",ans);

    return ;

}