#M. A query from Alice

传统题

3000ms

512MiB

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

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$ 的因子。