P0405

[NOI2024] 分数

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

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

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

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

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

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

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

输入格式

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

输出格式

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

样例输入

10 10

样例输出

16

样例解释

分子、分母均不超过 1010 的完美正分数共有 1616 个。其中小于 11 的八个为

12,14,16,18,110,25,29,49,\frac12,\frac14,\frac16,\frac18,\frac1{10},\frac25,\frac29,\frac49,

其余八个是它们的倒数。

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

数据范围

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

来源与许可

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

样例 2

输入

891 674

输出

8042

样例 3

输入

63691 63691

输出

4483786

样例 4

输入

891674 891674

输出

199940548