题意理解

我们需要统计所有满足 $1 \le x \le n$，$1 \le y \le m$ 的分数 $\frac{x}{y}$，在 $k$ 进制下是纯循环小数，并且只算数值不同的分数。

---

纯循环小数的条件

在 $k$ 进制下，一个既约分数 $\frac{x}{y}$ 是纯循环小数的充要条件是：
分母 $y$ 与 $k$ 互质（即 $\gcd(y, k) = 1$）。

这是因为：

• 如果 $y$ 含有 $k$ 的质因子，那么 $k$ 进制下该分数是有限小数或混循环小数。
• 如果 $y$ 与 $k$ 互质，则小数从第一位开始循环，是纯循环小数。

---

问题转化

我们要统计所有不同的 $\frac{x}{y}$ 值，其中：

• $1 \le x \le n$
• $1 \le y \le m$
• $\gcd(y, k) = 1$
• 只算不同的最简分数值。

注意：不同的 $\frac{x}{y}$ 值，就是不同的 $(x / \gcd(x,y), y / \gcd(x,y))$ 对，并且分母与 $k$ 互质。

---

数学形式

设 $d = \gcd(x, y)$，则 $\frac{x}{y} = \frac{x/d}{y/d}$，其中 $\gcd(x/d, y/d) = 1$。

条件 $\gcd(y/d, k) = 1$ 必须成立（因为分母必须与 $k$ 互质）。

所以我们要统计所有互质对 $(p, q)$ 满足：

• $1 \le p \le n$
• $1 \le q \le m$
• $\gcd(p, q) = 1$
• $\gcd(q, k) = 1$

并且 $p / q$ 互不相同（这里互质对天然互不相同）。

---

统计公式

设 $f(n, m, k)$ 表示满足：

• $1 \le p \le n$
• $1 \le q \le m$
• $\gcd(p, q) = 1$
• $\gcd(q, k) = 1$

的互质对 $(p, q)$ 的数量。

那么答案就是：

$$\sum_{q=1}^m [\gcd(q, k) = 1] \sum_{p=1}^n [\gcd(p, q) = 1] $$

---

化简

对于固定的 $q$，与 $q$ 互质的 $p$ 的数量是：

$$\sum_{p=1}^n [\gcd(p, q) = 1] = \sum_{d|q} \mu(d) \left\lfloor \frac{n}{d} \right\rfloor $$

其中 $\mu$ 是莫比乌斯函数。

因此：

$$\text{ans} = \sum_{q=1}^m [\gcd(q, k) = 1] \sum_{d|q} \mu(d) \left\lfloor \frac{n}{d} \right\rfloor $$

交换求和顺序：

$$\text{ans} = \sum_{d=1}^m \mu(d) \left\lfloor \frac{n}{d} \right\rfloor \sum_{\substack{q=1 \\ d|q}}^m [\gcd(q, k) = 1] $$

令 $q = d \cdot t$，则 $t \le \lfloor m/d \rfloor$，且 $\gcd(d t, k) = 1$。

因为 $\gcd(d t, k) = 1$ 等价于 $\gcd(d, k) = 1$ 且 $\gcd(t, k) = 1$。

所以：

$$\text{ans} = \sum_{d=1}^m \mu(d) \left\lfloor \frac{n}{d} \right\rfloor \cdot [\gcd(d, k) = 1] \cdot \sum_{t=1}^{\lfloor m/d \rfloor} [\gcd(t, k) = 1] $$

---

定义辅助函数

设：

$$S(n, k) = \sum_{i=1}^n [\gcd(i, k) = 1]$$

即 $1 \dots n$ 中与 $k$ 互质的数的个数。

那么：

$$\text{ans} = \sum_{d=1}^m \mu(d) \cdot [\gcd(d, k) = 1] \cdot \left\lfloor \frac{n}{d} \right\rfloor \cdot S\left( \left\lfloor \frac{m}{d} \right\rfloor, k \right) $$

---

高效计算

• $S(n, k)$ 可以用容斥原理在 $O(2^{\omega(k)})$ 时间内计算，其中 $\omega(k)$ 是 $k$ 的不同质因子个数，因为 $k \le 2000$，所以 $\omega(k)$ 很小。
• 我们还需要 $\mu(d)$ 且 $\gcd(d, k) = 1$ 的前缀和，用于整除分块。

设：

$$F(n) = \sum_{d=1}^n \mu(d) \cdot [\gcd(d, k) = 1]$$

我们可以用类似 Min25 筛的方法或直接容斥来求 $F(n)$，但这里 $n$ 可达 $10^9$，需要杜教筛。

---

杜教筛

我们要求：

$$F(n) = \sum_{d=1}^n \mu(d) [\gcd(d, k) = 1]$$

设 $g = \mu \cdot [\gcd(\cdot, k) = 1]$。

注意到 $[\gcd(n, k) = 1] = \sum_{e|k} \mu(e) [e|n]$ 的另一种形式是：

$$[\gcd(n, k) = 1] = \sum_{e|\gcd(n, k)} \mu(e)$$

其实更简单：$g(n) = \mu(n) \cdot [\gcd(n, k) = 1]$。

我们可以用 Dirichlet 卷积：

$$g * 1 = \sum_{d|n} \mu(d) [\gcd(d, k) = 1]$$

这等于 $[n=1]$ 吗？不一定，因为 $[\gcd(d, k) = 1]$ 破坏了完全积性。

更好的办法：注意到 $g = \mu \cdot \chi$，其中 $\chi(n) = [\gcd(n, k) = 1]$ 是模 $k$ 的平凡特征（完全积性）。那么：

$$(g * \chi)(n) = \sum_{d|n} \mu(d) [\gcd(d, k) = 1] \cdot [\gcd(n/d, k) = 1] $$

但 $\gcd(d, k) = 1$ 且 $\gcd(n/d, k) = 1$ 意味着 $\gcd(n, k) = 1$，此时 $g * \chi = \mu * 1 = \delta$（当 $\gcd(n, k) = 1$）。否则为 $0$。

所以：

$$\sum_{i=1}^n (g * \chi)(i) = 1$$

因为只有 $i=1$ 时非零。

于是：

$$\sum_{i=1}^n \sum_{d|i} g(d) \chi(i/d) = 1$$

交换求和：

$$\sum_{d=1}^n g(d) \sum_{t=1}^{\lfloor n/d \rfloor} \chi(t) = 1 $$

即：

$$\sum_{d=1}^n g(d) S(\lfloor n/d \rfloor, k) = 1$$

所以：

$$g(n) = \sum_{d=1}^n g(d) S(\lfloor n/d \rfloor, k) = 1 $$

移项：

$$g(1) S(n, k) + \sum_{d=2}^n g(d) S(\lfloor n/d \rfloor, k) = 1 $$

$g(1) = \mu(1) [\gcd(1, k) = 1] = 1$。

所以：

$$S(n, k) + \sum_{d=2}^n g(d) S(\lfloor n/d \rfloor, k) = 1 $$

于是：

$$g(n) = 1 - \sum_{d=2}^n g(d) S(\lfloor n/d \rfloor, k) $$

这给出了 $g$ 的前缀和的递归计算方法，可以杜教筛。

---

算法步骤

1. 预处理 $S(n, k)$ 的容斥计算。
2. 用杜教筛计算 $F(n) = \sum_{i=1}^n \mu(i) [\gcd(i, k) = 1]$。
3. 对答案式：

$$\text{ans} = \sum_{d=1}^m \mu(d) [\gcd(d, k) = 1] \cdot \left\lfloor \frac{n}{d} \right\rfloor \cdot S\left( \left\lfloor \frac{m}{d} \right\rfloor, k \right) $$

使用整除分块，每次需要 $F(r) - F(l-1)$ 和 $S(\lfloor m/d \rfloor, k)$。

---

时间复杂度

• 杜教筛 $O(n^{2/3})$ 预处理，查询 $O(n^{3/4})$ 或 $O(n^{2/3})$。
• 整除分块 $O(\sqrt{m})$ 次查询。
• 总复杂度大约 $O(n^{2/3} + m^{2/3})$ 。