计蒜客

  1. 题库
  2. 阿里云秘钥池
  3. 问答
  • 16.58%
  • 2500ms
  • 131072K

对于每个正整数 $n$,我们定义它的 $p$ 进制表示 由 $m$ 个非负整数 $a_1, a_2, \cdots, a_m$ 组成,并且这些数字满足 $\displaystyle n = \sum_{i = 1}^{m}{a_i p^{i - 1}}$,以及 $0 \leq a_i < p\ (i = 1, 2, \cdots, m - 1)$ 和 $1 \leq a_m < p$。

在阿里云台上,用户登录的秘钥都是由一个正整数组成。一个可被用作秘钥的正整数 $n$,它的 $p$ 进制表示需要满足 $1 \leq a_i < p\ (i = 1, 2, \cdots, m)$ 且 $\gcd(a_i, a_{i + 1}) = 1\ (i = 1, 2, \cdots, m - 1)$。比如当 $p = 10$ 时,$61$ 是一个合法秘钥,$3216$ 也是;但是当 $p = 100$ 时,$61$ 依旧是一个合法秘钥,$3216$ 却不是。

给出正整数 $L, R$ 和 $p$,请你统计满足 $L \leq n \leq R$ 并且 $n$ 是一个合法秘钥的正整数 $n$ 的数量。

输入格式

第一行包含一个正整数 $T(1 \leq T \leq 10^3)$,表示有 $T$ 组测试数据。

接下来依次给出每组测试数据,每组测试数据仅一行,包含三个正整数 $L, R(1 \leq L \leq R \leq 10^{18})$ 和 $p(2 \leq p \leq 10^5)$ ,含义见题目描述。

保证不超过 $50$ 组数据满足 $p > 10^3$。

输出格式

对于每组数据输出一行,包含一个整数,表示满足条件的数字数量。

样例输入

4
5 7 9
1 100 2
1 100 5
2017 2121 10

样例输出

3
6
41
10

题目来源

2017 计蒜之道 复赛

想挑战这道题吗

  • main.c