[NOI2024] 分数

[NOI2024] 分数

定义正分数为分子、分母都为正整数的既约分数。

定义完美正分数集合 $S$ 为满足以下五条性质的正分数集合：

1. $\dfrac{1}{2}\in S$；
2. 对于 $\dfrac{1}{2}<x<2$，$x\notin S$；
3. 对于所有 $x\in S$，$\dfrac{1}{x}\in S$；
4. 对于所有 $x\in S$，$x+2\in S$；
5. 对于所有 $x\in S$ 且 $x>2$，$x-2\in S$。

可以证明，上述五条性质确定了唯一的完美正分数集合 $S$。所有 $S$ 中的正分数被称为完美正分数。

记 $f(i,j)$ 表示 $\dfrac{i}{j}$ 是否为完美正分数：当且仅当 $i$ 与 $j$ 互素且 $\dfrac{i}{j}\in S$ 时，$f(i,j)=1$；否则 $f(i,j)=0$。

给定 $n,m$，求分子不超过 $n$、分母不超过 $m$ 的完美正分数数量，即

$$\sum_{i=1}^{n}\sum_{j=1}^{m}f(i,j).$$

输入格式

输入一行两个正整数 $n,m$，分别表示分子和分母的上界。

输出格式

输出一行一个非负整数，表示答案。

样例输入

10 10

样例输出

16

样例解释

分子、分母均不超过 $10$ 的完美正分数共有 $16$ 个。其中小于 $1$ 的八个为

$$\frac12,\frac14,\frac16,\frac18,\frac1{10},\frac25,\frac29,\frac49,$$

其余八个是它们的倒数。

例如，从 $\frac12$ 依次得到 $\frac52$、$\frac92$，再取倒数即可得到 $\frac29$。

数据范围

对于所有测试数据，$2\le n,m\le 3\times 10^7$。

来源与许可

本题为 CCF NOI 2024 第二试第一题「分数（fraction）」。题面与测试数据来自 NOI 官网发布页，按 CC BY-NC 4.0 使用。原赛制使用 fraction.in / fraction.out 文件输入输出；本平台等价适配为标准输入输出。

样例 1

输入

10 10

输出

16

样例 2

输入

891 674

输出

8042

样例 3

输入

63691 63691

输出

4483786

样例 4

输入

891674 891674

输出

199940548