English · Original
Chinese · Translation
Formal · Original
For given _n_, _l_ and _r_ find the number of distinct geometrical progression, each of which contains _n_ distinct integers not less than _l_ and not greater than _r_. In other words, for each progression the following must hold: _l_ ≤ _a__i_ ≤ _r_ and _a__i_ ≠ _a__j_ , where _a_1, _a_2, ..., _a__n_ is the geometrical progression, 1 ≤ _i_, _j_ ≤ _n_ and _i_ ≠ _j_.
Geometrical progression is a sequence of numbers _a_1, _a_2, ..., _a__n_ where each term after first is found by multiplying the previous one by a fixed non-zero number _d_ called the common ratio. Note that in our task _d_ may be non-integer. For example in progression 4, 6, 9, common ratio is .
Two progressions _a_1, _a_2, ..., _a__n_ and _b_1, _b_2, ..., _b__n_ are considered different, if there is such _i_ (1 ≤ _i_ ≤ _n_) that _a__i_ ≠ _b__i_.
## Input
The first and the only line cotains three integers _n_, _l_ and _r_ (1 ≤ _n_ ≤ 107, 1 ≤ _l_ ≤ _r_ ≤ 107).
## Output
Print the integer _K_ — is the answer to the problem.
[samples]
## Note
These are possible progressions for the first test of examples:
* 1;
* 2;
* 3;
* 4;
* 5;
* 6;
* 7;
* 8;
* 9;
* 10.
These are possible progressions for the second test of examples:
* 6, 7;
* 6, 8;
* 6, 9;
* 7, 6;
* 7, 8;
* 7, 9;
* 8, 6;
* 8, 7;
* 8, 9;
* 9, 6;
* 9, 7;
* 9, 8.
These are possible progressions for the third test of examples:
* 1, 2, 4;
* 1, 3, 9;
* 2, 4, 8;
* 4, 2, 1;
* 4, 6, 9;
* 8, 4, 2;
* 9, 3, 1;
* 9, 6, 4.
These are possible progressions for the fourth test of examples:
* 4, 6, 9;
* 9, 6, 4.
[{"iden":"statement","content":"给定 #cf_span[n]、#cf_span[l] 和 #cf_span[r]，求满足以下条件的互不相同的几何序列的个数：每个序列包含 #cf_span[n] 个互不相同的整数，且每个数都不小于 #cf_span[l] 且不大于 #cf_span[r]。换句话说，对于每个序列 #cf_span[a1, a2, ..., an]，必须满足 #cf_span[l ≤ ai ≤ r] 且 #cf_span[ai ≠ aj]，其中 #cf_span[1 ≤ i, j ≤ n] 且 #cf_span[i ≠ j]。\n\n几何序列是一个数列 #cf_span[a1, a2, ..., an]，其中每一项（除第一项外）都是由前一项乘以一个固定的非零常数 #cf_span[d]（称为公比）得到的。注意，在本题中 #cf_span[d] 可以是非整数。例如，在序列 #cf_span[4, 6, 9] 中，公比为 。\n\n两个序列 #cf_span[a1, a2, ..., an] 和 #cf_span[b1, b2, ..., bn] 被认为不同，当且仅当存在某个 #cf_span[i]（#cf_span[1 ≤ i ≤ n]）使得 #cf_span[ai ≠ bi]。\n\n输入仅一行，包含三个整数 #cf_span[n]、#cf_span[l] 和 #cf_span[r]（#cf_span[1 ≤ n ≤ 107, 1 ≤ l ≤ r ≤ 107]）。\n\n请输出整数 #cf_span[K] —— 本题的答案。\n\n以下是示例中第一个测试用例的可能序列：\n\n以下是示例中第二个测试用例的可能序列：\n\n以下是示例中第三个测试用例的可能序列：\n\n以下是示例中第四个测试用例的可能序列：\n\n"},{"iden":"input","content":"输入仅一行，包含三个整数 #cf_span[n]、#cf_span[l] 和 #cf_span[r]（#cf_span[1 ≤ n ≤ 107, 1 ≤ l ≤ r ≤ 107]）。"},{"iden":"output","content":"请输出整数 #cf_span[K] —— 本题的答案。"},{"iden":"examples","content":"输入1 1 10输出10输入2 6 9输出12输入3 1 10输出8输入3 3 10输出2"},{"iden":"note","content":"以下是示例中第一个测试用例的可能序列： #cf_span[1]; #cf_span[2]; #cf_span[3]; #cf_span[4]; #cf_span[5]; #cf_span[6]; #cf_span[7]; #cf_span[8]; #cf_span[9]; #cf_span[10]。以下是示例中第二个测试用例的可能序列： #cf_span[6, 7]; #cf_span[6, 8]; #cf_span[6, 9]; #cf_span[7, 6]; #cf_span[7, 8]; #cf_span[7, 9]; #cf_span[8, 6]; #cf_span[8, 7]; #cf_span[8, 9]; #cf_span[9, 6]; #cf_span[9, 7]; #cf_span[9, 8]。以下是示例中第三个测试用例的可能序列： #cf_span[1, 2, 4]; #cf_span[1, 3, 9]; #cf_span[2, 4, 8]; #cf_span[4, 2, 1]; #cf_span[4, 6, 9]; #cf_span[8, 4, 2]; #cf_span[9, 3, 1]; #cf_span[9, 6, 4]。以下是示例中第四个测试用例的可能序列： #cf_span[4, 6, 9]; #cf_span[9, 6, 4]。 "}]}
**Definitions**
Let $ n, l, r \in \mathbb{Z} $ with $ 1 \leq n \leq 10^7 $, $ 1 \leq l \leq r \leq 10^7 $.
A geometric progression of length $ n $ is a sequence $ (a_1, a_2, \dots, a_n) $ such that $ a_i = a_1 \cdot d^{i-1} $ for some $ a_1 \in \mathbb{R} $, $ d \in \mathbb{R} \setminus \{0\} $, and all $ a_i $ are distinct.
**Constraints**
1. $ a_i \in [l, r] \cap \mathbb{R} $ for all $ i \in \{1, \dots, n\} $
2. $ a_i \neq a_j $ for all $ i \neq j $
3. $ a_1, d $ such that all $ a_i $ are real numbers in $ [l, r] $
**Objective**
Count the number of distinct geometric progressions $ (a_1, a_2, \dots, a_n) $ satisfying the above, where two progressions are distinct if $ a_i \neq b_i $ for some $ i $.
API Response (JSON)
{
"problem": {
"name": "F. Geometrical Progression",
"description": {
"content": "For given _n_, _l_ and _r_ find the number of distinct geometrical progression, each of which contains _n_ distinct integers not less than _l_ and not greater than _r_. In other words, for each progre",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 4000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF758F"
},
"statements": [
{
"statement_type": "Markdown",
"content": "For given _n_, _l_ and _r_ find the number of distinct geometrical progression, each of which contains _n_ distinct integers not less than _l_ and not greater than _r_. In other words, for each progre...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "[{\"iden\":\"statement\",\"content\":\"给定 #cf_span[n]、#cf_span[l] 和 #cf_span[r]，求满足以下条件的互不相同的几何序列的个数：每个序列包含 #cf_span[n] 个互不相同的整数，且每个数都不小于 #cf_span[l] 且不大于 #cf_span[r]。换句话说，对于每个序列 #cf_span[a1, a2, ..., an]，必须...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n, l, r \\in \\mathbb{Z} $ with $ 1 \\leq n \\leq 10^7 $, $ 1 \\leq l \\leq r \\leq 10^7 $. \nA geometric progression of length $ n $ is a sequence $ (a_1, a_2, \\dots, a_n) $ such tha...",
"is_translate": false,
"language": "Formal"
}
]
}