CF758F Geometrical Progression

给定 $n$、$l$ 和 $r$，求在区间 $[l, r]$ 内，包含 $n$ 个互不相同且均为整数的不同等比数列的个数。换句话说，对于每一个等比数列 $\{a_1, a_2, ..., a_n\}$，都必须满足 $l \leq a_i \leq r$ 且 $a_i \neq a_j$（$1 \leq i, j \leq n$ 且 $i \neq j$）。 等比数列是指一个数列 $\{a_1, a_2, ..., a_n\}$，使得从第二项开始的每一项等于前一项乘以一个固定的非零数 $d$（称为公比）。注意在本题中，$d$ 可以为非整数。例如，数列 $4, 6, 9$ 的公比为 $\frac{3}{2}$。 如果有某个 $i$（$1 \leq i \leq n$）使得 $a_i \neq b_i$，则数列 $\{a_1, a_2, ..., a_n\}$ 和 $\{b_1, b_2, ..., b_n\}$ 被认为是不同的。

第一行包含三个整数 $n$、$l$ 和 $r$（$1 \leq n \leq 10^7,\ 1 \leq l \leq r \leq 10^7$）。

输出一个整数 $K$，表示满足条件的等比数列的个数。

以下是前几个示例对应的所有可能数列： - $1$； - $2$； - $3$； - $4$； - $5$； - $6$； - $7$； - $8$； - $9$； - $10$。 第二组样例可能的等比数列为： - $6, 7$； - $6, 8$； - $6, 9$； - $7, 6$； - $7, 8$； - $7, 9$； - $8, 6$； - $8, 7$； - $8, 9$； - $9, 6$； - $9, 7$； - $9, 8$。 第三组样例可能的等比数列为： - $1, 2, 4$； - $1, 3, 9$； - $2, 4, 8$； - $4, 2, 1$； - $4, 6, 9$； - $8, 4, 2$； - $9, 3, 1$； - $9, 6, 4$。 第四组样例可能的等比数列为： - $4, 6, 9$； - $9, 6, 4$。 由 ChatGPT 5 翻译