题目背景

本题时限3s

友情提示：https://www.luogu.org/problem/show?pid=3601

题目描述

题目还是简单一点好。

我们定义莫比乌斯函数$\mu(x)$，如果x的每个素因子只出现一次，有p个素因子，那么$\mu(x)=(-1)^p$，否则$\mu(x)=0$。

这题要求你求出$\sum_{i=l}^r \mu(i)$。

输入格式

一行两个整数，l、r。

输出格式

一行一个整数表示答案。

1 233

-1

99999999999899999 99999999999999999

421

提示

对于10%的数据，$l,r \leq 10^6$。

对于30%的数据，$l,r \leq 10^{12}$。

对于100%的数据，$1 \leq l \leq r \leq 10^{18}$，$r-l \leq 10^5$。