P10788 [NOI2024] 分数

由于评测机性能差异，原题时限为 6s，洛谷时限为 9s。

小 Y 和小 C 在玩一个游戏。 定义正分数为分子、分母都为正整数的既约分数。 定义**完美正分数集合** $S$ 为满足以下五条性质的正分数集合： - $\dfrac{1}{2}\in S$； - 对于 $\dfrac{1}{2}

输入的第一行包含两个正整数 $n$ 和 $m$，分别表示分子和分母的范围。

输出一行包含一个非负整数，表示对应的答案。

**【样例 1 解释】** 可以证明，分子分母均不超过 $10$ 的完美正分数共有 $16$ 个，其中小于 $1$ 的 $8$ 个如下： - $\dfrac{1}{2},\dfrac{1}{4},\dfrac{1}{6},\dfrac{1}{8},\dfrac{1}{10},\dfrac{2}{5},\dfrac{2}{9},\dfrac{4}{9}$。 大于 $1$ 的 $8$ 个完美正分数分别为上述 $8$ 个小于 $1$ 的完美正分数的倒数。 - 可以按照如下方式验证 $\dfrac{2}{9}$ 是否为完美正分数：因为 $\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$； - 可以按照如下方式验证 $\dfrac{3}{7}$ 是否为完美正分数：假设 $\dfrac{3}{7}$ 是完美正分数，则 $\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$，与第二条性质矛盾，因此 $\dfrac{3}{7}$ 不是完美正分数 **【数据范围】** 对于所有测试数据保证：$2\leq n,m\leq 3\times 10^7$。 ::cute-table{tuack} | 测试点编号 | $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$ | ^ |