P5946 [POI 2002 R3] B-Smooth 数

题目描述

$B$ 是一个正整数。

如果一个自然数 $n$ 被称为 $B$-smooth 数，那么它的质因子中没有任何一个超过 $B$。

我们说和 $n$ 等价的一个 $B$-smooth 数是指它能够表示成小于或等于 $B$ 的正整数乘积。

你的任务是对给定的闭区间 $[n,n+m]$，求出他们中的 $B$-smooth 数的个数。

输入格式

第一行是三个整数 $n,m$ 和 $B$。

输出格式

求出 $B$-smooth 数的个数。

输入输出样例 #1

输入 #1

30 10 5

输出 #1

4

说明/提示

对于 $100\%$ 的数据，$1\le n\le 2\times 10^9$，$1\le m\le 10^8$，$1\le B\le 10^6$。