4016. [NOI 2024]分数

【题目描述】

小 Y 和小 C 在玩一个游戏。

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

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

· $\frac{1}{2}\in S$；

· 对于 $\frac{1}{2}<x<2$，$x\not \in S$；

· 对于所有 $x\in S$，$\frac{1}{x}\in S$；

· 对于所有 $x\in S$，$x+2 \in S$；

· 对于所有 $x\in S$ 且 $x>2$，$x-2 \in S$；

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

所有完美正分数集合 $S$ 中的正分数被称为完美正分数。记 $f(i,j)$ 表示 $\frac{i}{j}$ 是否为完美正分数，即 $f(i,j)=1$ 当且仅当 $i$ 与 $j$ 互素且 $\frac{i}{j} \in S$，否则 $f(i,j)=0$。

小 C 问小 Y：给定 $n,m$，求所有分子不超过 $n$，分母不超过 $m$ 的完美正分数的个数，即求 $\sum_{i=1}^n \sum_{j=1}^m f(i,j)$。

时光走过，小 C 和小 Y 会再遇见。回首往事，大家都过上了各自想要的生活。

【输入格式】

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

【输出格式】

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

【样例输入】

10 10

【样例输出】

16

【样例2~4】

样例下载

样例2满足测试点 4-6 的约束条件

样例3满足测试点 11-14 的约束条件

样例4满足测试点 15-17 的约束条件

【样例1说明】

可以证明，分子分母均不超过 $10$ 的完美正分数共有 $16$ 个，其中小于 $1$ 的 $8$ 个如下：

· $\frac{1}{2},\frac{1}{4},\frac{1}{6},\frac{1}{8},\frac{1}{10},\frac{2}{5},\frac{2}{9},\frac{4}{9}$。

大于 $1$ 的 $8$ 个完美正分数分别为上述 $8$ 个小于 $1$ 的完美正分数的倒数。

· 可以按照如下方式验证 $\frac{2}{9}$ 是否为完美正分数：因为 $\frac{1}{2}\in S$，$\frac{1}{2}+2=\frac{5}{2}\in S$，$\frac{5}{2}+2=\frac{9}{2}\in S$，$\frac{1}{\frac{9}{2}}=\frac{2}{9}\in S$；

· 可以按照如下方式验证 $\frac{3}{7}$ 是否为完美正分数：假设 $\frac{3}{7}$ 是完美正分数，则 $\frac{1}{\frac{3}{7}}=\frac{7}{3}\in S$，$\frac{7}{3}-2=\frac{1}{3}\in S$，$\frac{1}{\frac{1}{3}}=3\in S$，$3-2=1\in S$，与第二条性质矛盾，因此 $\frac{3}{7}$ 不是完美正分数

【数据规模与约定】

对于所有测试数据保证：$2\leq n,m\leq 3\times 10^7$。

【来源】

NOI2024 Day2 Task1