题目背景

本题时限 3s

友情提示：https://www.luogu.com.cn/problem/P3601

题目描述

题目还是简单一点好。

我们定义莫比乌斯函数 $\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$。