Background

Time limit: 3 s.

Friendly reminder: https://www.luogu.com.cn/problem/P3601.

Problem Description

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)$.

Input Format

One line contains two integers $l,r$.

Output Format

One line contains one integer representing the answer.

1 233

-1

99999999999899999 99999999999999999

421

Hint

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