开始 2022-02-09 07:40:00

2022年寒假第二段新知日

结束 2022-02-10 18:00:00
比赛已经结束
当前 2024-11-20 00:45:14

C. 幸运数

描述

将正整数排列起来,删除偶数。而后依次删除第2×m个数、第3×m个数、第4×m个数(1 \le m)……最后会剩下一些数,这些数“幸运”的没有被删除掉。

注意:

k次删除的是剩余数中第k+1个的m倍位置上的数,具体来说,将整数排列好:

1, 2, 3, 4, 5, 6, 7, 8, 9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25

把偶数位置的数删除:

1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25

第1次删除时,k=1,k+1=2,第2个数是3,会把位置为3的正整数倍位置上的数的删除(上一行标为红色):

1, 3, 7, 9, 13, 15, 19, 21, 25

第2次删除时,k=2,k+1=3,第3个数是7,会把位置为7的正整数倍位置上的数删除(上一行标为红色):

1, 3, 7, 9, 13, 15, 21, 25

100以内的幸运数共有23个。

输入

共一行,两个正整数m,n

对于100%的数据:

1 \le m \le n \le 10^5

输出

(m,n)范围内幸运数个数。不含m,n

样例

输入

1 20

输出

5

输入

1 100

输出

22

输入

30 69

输出

8

提交

登录

注册
时间限制 1000 毫秒
内存限制 128 MB
提交