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

//
//  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+5,MOD=666623333;
inline ll read(){
    char c=getchar();ll x=0,f=1;
    while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1; c=getchar();}
    while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘; 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=2;i<=n;i++){
        if(!notp[i]) p[++p[0]]=i;
        for(int j=1;j<=p[0]&&i*p[j]<=n;j++){
            notp[i*p[j]]=1;
            if(i%p[j]==0) break;
        }
    }
}
ll phi[N],x[N];
void solve(){
    for(int i=1;i<=r-l+1;i++) x[i]=phi[i]=i+l-1;
    for(int i=1;i<=p[0];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+1]=phi[j-l+1]/p[i]*(p[i]-1);
            while(x[j-l+1]%p[i]==0) x[j-l+1]/=p[i];
        }
    }
    for(int i=1;i<=r-l+1;i++) if(x[i]>1) phi[i]=phi[i]/x[i]*(x[i]-1);
    //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)+1);
    solve();
    for(ll i=1;i<=r-l+1;i++) (ans+=i+l-1-phi[i])%=MOD;
    printf("%lld",ans);
    return 0;
}