题目背景
这是一道签到题！
建议做题之前仔细阅读数据范围！
题目描述
我们定义一个函数：qiandao(x)为小于等于x的数中与x不互质的数的个数。
这题作为签到题，给出l和r，要求求
。
输入输出格式
输入格式：
一行两个整数，l、r。
输出格式：
一行一个整数表示答案。
输入输出样例
输入样例#1：
233 2333
输出样例#1：
1056499
输入样例#2：
2333333333 2333666666
输出样例#2：
153096296
说明
对于30%的数据，
。
对于60%的数据，
。
对于100%的数据，
，
。
qiandao(x)=x-phi(x)，转化为求欧拉函数，而x只可能有一个大于n^0.5的素因子，所以只要求到n^0.5的素数就行了。还是批量处理欧拉函数的值，否则TLE啊。
program rrr(input,output);
const
cs=;
var
a:array[..]of boolean;
f,c:array[..]of int64;
i,j,n:longint;
l,r,k,ans:int64;
begin
assign(input,'r.in');assign(output,'r.out');reset(input);rewrite(output);
readln(l,r);
n:=trunc(sqrt(r));
fillchar(a,sizeof(a),true);
k:=l;while k<=r do begin f[k-l]:=k;c[k-l]:=k;inc(k); end;
for i:= to n do
if a[i] then
begin
k:=l div i*i;if k<l then k:=k+i;
while k<=r do
begin
f[k-l]:=f[k-l] div i*(i-);
while c[k-l] mod i= do c[k-l]:=c[k-l] div i;
k:=k+i;
end;
j:=i<<;while j<=n do begin a[j]:=false;j:=j+i; end;
end;
k:=l;while k<=r do begin if c[k-l]> then f[k-l]:=f[k-l] div c[k-l]*(c[k-l]-);inc(k); end;
ans:=;
k:=l;while k<=r do begin ans:=(ans+k-f[k-l]) mod cs;inc(k); end;
write(ans);
close(input);close(output);
end.
