#L4209. 「NOI2024」分数

「NOI2024」分数

题目描述:

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

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

定义完美正分数集合 SS 为满足以下五条性质的正分数集合:

  1. 12S\dfrac{1}{2} \in S
  2. 对于 12<x<2\dfrac{1}{2} < x < 2xSx \notin S
  3. 对于所有 xSx \in S1xS\dfrac{1}{x} \in S
  4. 对于所有 xSx \in Sx+2Sx+2 \in S
  5. 对于所有 xSx \in Sx>2x > 2x2Sx-2 \in S

可以证明,上述五条性质确定了唯一的完美正分数集合 SS

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

小 C 问小 Y:给定 n,mn,m,求所有分子不超过 nn,分母不超过 mm 的完美正分数的个数,即求

i=1nj=1mf(i,j)\sum_{i=1}^n \sum_{j=1}^m f(i,j)。

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


输入格式

从文件 fraction.in 中读入数据。

输入的第一行包含两个正整数 nnmm,分别表示分子和分母的范围。


输出格式

输出到文件 fraction.out 中。

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


样例 1

输入

10 10

输出

16

解释 可以证明,分子分母均不超过 1010 的完美正分数共有 1616 个,其中小于 1188 个如下:

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

大于 1188 个完美正分数分别为上述 88 个小于 11 的完美正分数的倒数。

可以按照如下方式验证 29\dfrac{2}{9} 是否为完美正分数: 因为 12S\dfrac{1}{2}\in S12+2=52S\dfrac{1}{2}+2=\dfrac{5}{2}\in S52+2=92S\dfrac{5}{2}+2=\dfrac{9}{2}\in S192=29S\dfrac{1}{\frac{9}{2}}=\dfrac{2}{9}\in S

可以按照如下方式验证 37\dfrac{3}{7} 是否为完美正分数: 假设 37\dfrac{3}{7} 是完美正分数,则 137=73S\dfrac{1}{\frac{3}{7}}=\dfrac{7}{3}\in S732=13S\dfrac{7}{3}-2=\dfrac{1}{3}\in S113=3S\dfrac{1}{\frac{1}{3}}=3\in S32=1S3-2=1\in S,与第二条性质矛盾,因此 37\dfrac{3}{7} 不是完美正分数。


数据范围

对于所有测试数据保证:2n,m3×1072 \leq n, m \leq 3 \times 10^7

测试点编号 nn \leq mm \leq
131 \sim 3 10210^2
464 \sim 6 10310^3
7107 \sim 10 80008\,000
111411 \sim 14 10510^5
151715 \sim 17 10610^6
1818 8×1068 \times 10^6
1919 3×1073 \times 10^7
2020 3×1073 \times 10^7