#P10381. [2021年联测]光滑数
[2021年联测]光滑数
题目描述
给定整数 ,求闭区间 中有多少个 -光滑数。
若一个正整数的所有质因子都不大于 ,就称它是 -光滑数。 没有质因子,因此也计入。
输入格式
一行三个整数 。
输出格式
一行一个整数,表示答案。
样例
1 10 4
7
其中 是 -光滑数。
123456789 987654321 2333
85775448
数据范围
,。
| 测试点 | 特殊限制 |
|---|---|
| 1 | |
| 2–3 | |
| 4–5 | |
| 6–7 | |
| 8–10 | 无 |
给定整数 L,R,p,求闭区间 [L,R] 中有多少个 p-光滑数。
若一个正整数的所有质因子都不大于 p,就称它是 p-光滑数。1 没有质因子,因此也计入。
一行三个整数 L,R,p。
一行一个整数,表示答案。
1 10 4
7
其中 1,2,3,4,6,8,9 是 4-光滑数。
123456789 987654321 2333
85775448
1≤L≤R≤1010,1≤p≤106。
| 测试点 | 特殊限制 |
|---|---|
| 1 | R≤103 |
| 2–3 | R≤5×106 |
| 4–5 | R−L≤5×106 |
| 6–7 | R≤108 |
| 8–10 | 无 |