$\begin{aligned}&\sf\small \ \ \ \ \color{grey}{On}\ \color{green}{lomienyeet}\color{grey}\rightarrow\color{blue}{\underline{Worsening\ Codeforces\ blog\ qualities?}}\color{grey}{,3\ months\ ago}\ |\star\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \color{grey}{-41}\\ &\sf\ \ \ \ \small so\ what\ do\ you\ want\ to\ express\ by\ writing\ this\ post\end{aligned}$
by WRuperD @ 2022-10-22 11:10:17
$\begin{aligned}&\sf\small \ \ \ \ \color{grey}{On}\ \color{green}{lomienyeet}\color{grey}\rightarrow\color{blue}{\underline{Worsening\ Codeforces\ blog\ qualities?}}\color{grey}{,3\ months\ ago}\ |\star\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \color{grey}{-41}\\ &\sf\ \ \ \ \small so\ what\ do\ you\ want\ to\ express\ by\ writing\ this\ post\end{aligned}$
by Yizhixiaoyun @ 2022-10-22 11:11:42
~~(红名好意思说自己是萌新)~~先这样，再这样……好了，你学废了吗
by zi_jin @ 2022-10-22 11:14:09
建议重学数论再来做这个题捏
by LuoTianyi_Official @ 2022-10-22 11:19:55
建议重学数论再来做这个题捏
by m256i @ 2022-10-22 11:28:40
不建议大家阴阳怪气捏
这是个欧拉函数啊，你不学怎么做得出来
by ass_wecan @ 2022-10-22 11:37:34
@[ass_wecan](/user/505805) 对啊，欧拉函数求每个数的时间复杂度是 $O(sqrt(n)*logn)$ ,那么总时间复杂度就赢个是 $O(nlogn)$ 啊！
by YuRuochen @ 2022-10-22 11:56:04
@[YuRuochen](/user/658786) 那你就学线性筛欧拉函数啊
by ass_wecan @ 2022-10-22 15:19:49
@[ass_wecan](/user/505805) 我似乎懂了些什么，所以现在开始大干代码，结果……
by YuRuochen @ 2022-10-22 15:37:02
@[ass_wecan](/user/505805) 在半小时前，我突然萌发思路，于是写了半个小时代码，终于AC了。。。
```cpp
#include<bits/stdc++.h>
#define int __int128
using namespace std;
int l,r,ans,A[1000010],B[1000010],t[1000010];
bool noPM[1000010];
vector<int> prime;
int read(){
char c=getchar();
while(c<48||c>57) c=getchar();
int num=0;
while(c>=48&&c<=57){
num=(num<<3)+(num<<1)+c-48;
c=getchar();
}
return num;
}
void print(int num){
if(num){
stack<int> st;
while(num){
st.push(num%10);
num/=10;
}
while(!st.empty()){
putchar(st.top()+48);
st.pop();
}
}else putchar(48);
}
signed main(){
l=read();
r=read();
for(int i=2;i<=1000;i++){
if(!noPM[i]){
for(int j=i*i;j<=1000000;j+=i) noPM[j]=1;
}
}
for(int i=2;i<=1000000;i++){
if(!noPM[i]) prime.push_back(i);
}
for(int i=0;i<=r-l;i++){
A[i]=B[i]=1;
t[i]=i+l;
}
for(int i=0;i<prime.size()&&prime[i]*prime[i]<=r;i++){
int p=prime[i];
for(int j=r/p*p;j>=l;j-=p){
A[j-l]*=p-1;
B[j-l]*=p;
while(t[j-l]%p==0) t[j-l]/=p;
}
}
for(int i=l;i<=r;i++){
int f;
if(t[i-l]==1) f=i/B[i-l]*A[i-l];
else f=i/B[i-l]*A[i-l]*(t[i-l]-1)/t[i-l];
ans=(ans+i-f)%666623333;
}
print(ans);
return 0;
}
```
by YuRuochen @ 2022-10-22 15:40:48