#P10381. [2021年联测]光滑数

    ID: 9499 传统题 2000ms 512MiB 尝试: 9 已通过: 1 难度: 9 上传者: 标签>CF2600提高+/省选-阈值划分大小情况线性筛最小质因子预处理离线查询树状数组

[2021年联测]光滑数

题目描述

给定整数 L,R,pL,R,p,求闭区间 [L,R][L,R] 中有多少个 pp-光滑数。

若一个正整数的所有质因子都不大于 pp,就称它是 pp-光滑数。11 没有质因子,因此也计入。

输入格式

一行三个整数 L,R,pL,R,p。

输出格式

一行一个整数,表示答案。

样例

1 10 4
7

其中 1,2,3,4,6,8,91,2,3,4,6,8,9 是 44-光滑数。

123456789 987654321 2333
85775448

数据范围

1≤L≤R≤10101\le L\le R\le10^{10},1≤p≤1061\le p\le10^6。

测试点 特殊限制
1 R≤103R\le10^3
2–3 R≤5×106R\le5\times10^6
4–5 R−L≤5×106R-L\le5\times10^6
6–7 R≤108R\le10^8
8–10 无

原 PDF 题面