UOJ Logo Universal Online Judge

UOJ

#896. 【NOI2024】分数

附件下载 统计

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

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

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

  1. 12S
  2. 对于 12<x<2xS
  3. 对于所有 xS1xS
  4. 对于所有 xSx+2S
  5. 对于所有 xSx>2x2S

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

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

小 C 问小 Y:给定 n,m,求所有分子不超过 n,分母不超过 m 的完美正分数的个数,即求 i=1nj=1mf(i,j)

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

输入格式

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

输出格式

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

样例一

input

10 10

output

16

explanation

可以证明,分子分母均不超过 10 的完美正分数共有 16 个,其中小于 18 个如下:

  • 12,14,16,18,110,25,29,49

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

  • 可以按照如下方式验证 29 是否为完美正分数:因为 12S12+2=52S52+2=92S192=29S,所以 29 是完美正分数。
  • 可以按照如下方式验证 37 是否为完美正分数:假设 37 是完美正分数,则 137=73S732=13S113=3S32=1S,与第二条性质矛盾,因此 37 不是完美正分数。

样例二

见附件下载中的 ex_fraction2.inex_fraction2.ans

这个样例满足测试点 46 的约束条件。

样例三

见附件下载中的 ex_fraction3.inex_fraction3.ans

这个样例满足测试点 1114 的约束条件。

样例四

见附件下载中的 ex_fraction4.inex_fraction4.ans

这个样例满足测试点 1517 的约束条件。

数据范围

对于所有测试数据保证:2n,m3×107

测试点编号 n m
13 102 102
46 103 103
710 8000 8000
1114 105 105
1517 106 106
18 8×106 8×106
19 3×107
20 3×107

时间限制:6s12s

空间限制:512MB