P3653 A Fresh Math Problem

Time limit: 3 s. Friendly reminder: https://www.luogu.com.cn/problem/P3601.

Let's keep the problem simple. We define the Möbius function $\mu(x)$. If each prime factor of $x$ appears only once and there are $p$ prime factors, then $\mu(x)=(-1)^p$; otherwise, $\mu(x)=0$. You are asked to compute $\sum_{i=l}^r \mu(i)$.

One line contains two integers $l,r$.

One line contains one integer representing the answer.

For $10\%$ of the testdata, $l,r \leq 10^6$. For $30\%$ of the testdata, $l,r \leq 10^{12}$. For $100\%$ of the testdata, $1 \leq l \leq r \leq 10^{18}$, $r-l \leq 10^5$. Translated by ChatGPT 5