#P2980. [Poi2002]B-Smooth 数

    ID: 2101 传统题 1000ms 512MiB 尝试: 58 已通过: 15 难度: 6 上传者: 标签>CF2100提高深度优先搜索可行性剪枝对称性去重线性筛一维前缀和

[Poi2002]B-Smooth 数

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

题目描述

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

输入格式

第一行有用单个空格分隔的三个整数 n,mn, m 和 BB。

输出格式

求出 BB-smooth 数的个数.

样例输入

30 10 5

样例输出

4

数据规模与约定

对于 100%100\% 的数据,1≤n≤2×1091\leq n\leq 2\times 10^9,1≤m≤1×1081\leq m\leq 1\times 10^8,1≤B≤1×1061\leq B\leq 1\times 10^6。