← 返回题目列表

Codeforces · 83/D

D. 数字

中文机器翻译题面 查看原题

瓦莱拉(Valera)在很平常的一天去上学(工作日他没有其他地方应该去)。在数学课上,他最喜欢的老师埃文斯女士向学生们介绍了除数。尽管瓦莱拉热爱数学,但他对这个特定的话题并不感兴趣。更重要的是,上课太无聊了,他竟然睡着了。而只有一声响亮的放学铃声才能打断他的美梦。

当然,宝贵的资料和老师的讲解都丢失了。然而,瓦莱拉无论如何都必须做足功课。由于他对新材料并不完全了解,他无法自己完成这项工作。这就是为什么他请你帮忙。毕竟你是他最好的朋友,你不能拒绝帮助。

Valera 的家庭任务只有一个问题,虽然以一种非常简单的方式表述,但没有一个简单的解决方案。它的语句如下:如果我们考虑区间 [a;b] 中的所有正整数,那么需要计算该区间中最小除数为某个整数 k 的数字的数量(不必考虑除数等于 1)。换句话说,您应该计算区间 [a;b] 中此类数字的数量,这些数字不能被 2 到 k - 1 之间的任何数字整除,但可以被 k 整除。

输入

第一行也是唯一一行包含三个正整数 a、b、k (1 ≤ a ≤ b ≤ 2·109, 2 ≤ k ≤ 2·109)。

输出

在一行上打印给定问题的答案。

示例

输入 #1

1 10 2

输出 #1

5

输入 #2

12 23 3

输出 #2

2

输入 #3

6 19 5

输出 #3

0

注意

对声明中样本的评论:

在第一个示例中,答案是数字 2、4、6、8、10。

第二个 — 15, 21

第三个中没有这样的数字。