P10788 [NOI2024] Fractions

Due to differences in the performance of judging machines, the original time limit was 6 s, and the Luogu time limit is 9 s.

Xiao Y and Xiao C are playing a game. A positive fraction is defined as an irreducible fraction whose numerator and denominator are both positive integers. A **perfect positive fraction set** $S$ is a set of positive fractions that satisfies the following five properties: - $\dfrac{1}{2}\in S$; - For $\dfrac{1}{2}

The first line contains two positive integers $n$ and $m$, representing the ranges of the numerator and denominator, respectively.

Output one line containing a non-negative integer, representing the corresponding answer.

**[Sample 1 Explanation]** It can be proven that there are $16$ perfect positive fractions with both numerator and denominator not exceeding $10$. The $8$ that are less than $1$ are: - $\dfrac{1}{2},\dfrac{1}{4},\dfrac{1}{6},\dfrac{1}{8},\dfrac{1}{10},\dfrac{2}{5},\dfrac{2}{9},\dfrac{4}{9}$. The $8$ perfect positive fractions greater than $1$ are the reciprocals of the above $8$ perfect positive fractions less than $1$. - You can verify whether $\dfrac{2}{9}$ is a perfect positive fraction as follows: since $\dfrac{1}{2}\in S$, $\dfrac{1}{2}+2=\dfrac{5}{2}\in S$, $\dfrac{5}{2}+2=\dfrac{9}{2}\in S$, $\dfrac{1}{\dfrac{9}{2}}=\dfrac{2}{9}\in S$; - You can verify whether $\dfrac{3}{7}$ is a perfect positive fraction as follows: assume $\dfrac{3}{7}$ is a perfect positive fraction, then $\dfrac{1}{\dfrac{3}{7}}=\dfrac{7}{3}\in S$, $\dfrac{7}{3}-2=\dfrac{1}{3}\in S$, $\dfrac{1}{\dfrac{1}{3}}=3\in S$, $3-2=1\in S$, which contradicts the second property. Therefore, $\dfrac{3}{7}$ is not a perfect positive fraction. **[Constraints]** For all testdata, it is guaranteed that $2\leq n,m\leq 3\times 10^7$. ::cute-table{tuack} | Test Point ID | $n\leq$ | $m\leq$ | | :----------: | :----------: | :----------: | | $1\sim 3$ | $10^2$ | $10^2$ | | $4\sim 6$ | $10^3$ | $10^3$ | | $7\sim 10$ | $8\,000$ | $8\,000$ | | $11\sim 14$ | $10^5$ | $10^5$ | | $15\sim 17$ | $10^6$ | $10^6$ | | $18$ | $8\times 10^6$ | $8\times 10^6$ | | $19$ | ^ | $3\times 10^7$ | | $20$ | $3\times 10^7$ | ^ | Translated by ChatGPT 5