bzoj#P2980. [POI2002]B-Smooth 数

[POI2002]B-Smooth 数

//时间限制:10s 空间限制:128MB

题目描述

BB 是一个正整数. 如果一个自然数 nn 被称为 BB-smooth 数,那么它的质因素中没有任何一个超过 BB。我们说和 nn 等价的一个 BB-smooth 数,如果它能够表示成小于或等于 BB 的正整数乘积。你的任务是对给定的闭区间 [n,n+m][n,n+m],求出他们中的 BB-smooth 数的个数。

输入格式

第一行有用单个空格分隔的三个整数 n,mn, mBB

输出格式

求出 BB-smooth 数的个数.

样例输入

30 10 5

样例输出

4

数据规模与约定

对于 100%100\% 的数据,1n2×1091\leq n\leq 2\times 10^91m1×1081\leq m\leq 1\times 10^81B1×1061\leq B\leq 1\times 10^6