← 返回题目列表

Codeforces · 758/F

F. 几何级数

中文机器翻译题面 查看原题

对于给定的 n、l 和 r,求不同几何级数的数量,每个几何级数包含 n 个不小于 l 且不大于 r 的不同整数。换句话说,对于每个级数,必须满足以下条件:l ≤ ai ≤ r 且 ai ≠ aj ,其中 a1、a2、...、an 是几何级数,1 ≤ i、j ≤ n 且 i ≠ j。

几何级数是一个数字 a1、a2、...、an 的序列,其中第一项之后的每一项都是通过将前一项乘以一个固定的非零数字 d(称为公比)来找到的。请注意,在我们的任务中 d 可能是非整数。例如,在级数 4、6、9 中,公比为 $$d=\frac{3}{2}$$。

如果存在这样的 i (1 ≤ i ≤ n) 并且 ai ≠ bi,则两个级数 a1, a2, ..., an 和 b1, b2, ..., bn 被认为是不同的。

输入

第一行也是唯一一行包含三个整数 n、l 和 r (1 ≤ n ≤ 107, 1 ≤ l ≤ r ≤ 107)。

输出

打印整数 K — 就是问题的答案。

示例

输入 #1

1 1 10

输出 #1

10

输入 #2

2 6 9

输出 #2

12

输入 #3

3 1 10

输出 #3

8

输入#4

3 3 10

输出#4

2

注意

这些是示例的第一次测试的可能进展:

- 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.