A query from Alice

ID: 916

传统题

3000ms

512MiB

尝试: 14

已通过: 2

难度: 9

上传者:

Hydro

标签>

其他

数学

整除分块

第四届校赛题目

Description

$Bob$ 很喜欢拿自己做过的但是很难的题来折磨 $Alice$ ，今天 $Bob$ 在做完一道题后觉得这道题太简单了，所以他对题目进行了强化，然后给了 $Alice$ 试图折磨他。

他给了这样一道题目: 定义 $\lfloor x \rfloor$ 为对 $x$ 下取整，例如 $\lfloor 3 \rfloor = 3，\lfloor 2.1 \rfloor = 2， \lfloor 2.9 \rfloor = 2$ ， $\lfloor \sqrt x \rfloor$ 为对 $x$ 进行开平方后下取整，例如 $\lfloor \sqrt 5 \rfloor = 2， \lfloor \sqrt 4 \rfloor = 2， \lfloor \sqrt 3 \rfloor = 1$ ， $\lfloor \sqrt[k]x \rfloor$ 为对 $x$ 开 $k$ 次方后下取整。给定三个整数 $l，r，k$ ，问有多少个数 $x$ 满足 $l\leq x \leq r$ 且 $\lfloor \sqrt[k]x \rfloor$ 是 $x$ 的因子。