Geometrical Progression
Contest: Codeforces Round 392 (Div. 2)
Difficulty rating: 2400
Tags: brute force, math, number theory

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 ≤ ai ≤ r and ai ≠ aj , where a1, a2, ..., an is the geometrical progression, 1 ≤ i, j ≤ n and i ≠ j.

Geometrical progression is a sequence of numbers a1, a2, ..., an 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 $$d=\frac{3}{2}$$.

Two progressions a1, a2, ..., an and b1, b2, ..., bn are considered different, if there is such i (1 ≤ i ≤ n) that ai ≠ bi.

Input format:
The first and the only line cotains three integers n, l and r (1 ≤ n ≤ 107, 1 ≤ l ≤ r ≤ 107).

Output format:
Print the integer K — is the answer to the problem.

Constraints:
Time limit: 4.0 s
Memory limit: 256.0 MB

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.

Example input:
1 1 10

Example output:
10

Example input:
2 6 9

Example output:
12

Editorial:
Let d — is the denominator of the progression. d — is the rational number, because all numbers of progression are integers. $$d = \frac{x}{y}$$,where x, y — are integers, gcd(x, y) = 1. Then $$a_{n} = a_{1} \cdot \frac{x^{n-1}}{y^{n-1}}$$. Because all numbers of progression are integers, so $$a_{1}:y^{n-1}$$. Let $$b = \frac{a_1}{y^{n-1}}$$, then a1 = b·yn - 1 and an = b·xn - 1.
According to the condition of the problem it must be done: l ≤ b·yn - 1 ≤ r и l ≤ b·xn - 1 ≤ r.
Count the number of increasing progressions, it means d > 1 (y < x). Note that there are decreasing progressions as much as increasing, any decreasing progression   — is increasing, but written from right to left.
If y < x, then l ≤ b·yn - 1 < b·xn - 1 ≤ r.
Then for certain x and y the number of possible integers b is calculated by the formula $$\frac{r}{x^{n-1}} - \frac{l}{y^{n-1}}$$.
Let's sort y from 1 to $$\sqrt[n-1]{r}$$, x from y + 1 to $$\sqrt[n-1]{r}$$. Before you add the number of options for the next x and y you need to check that gcd(x, y) = 1. Better to count gcd(x, y) using Euclidean algorithm for $${\mathcal {O}}(\log ^{3}n)$$. Remember that we counted only increasing progressions, the answer would be higher twice.
Note that when n = 1 this algorithm is meaningless, so it is necessary to separately register the answer, for n = 1 it equals r - l + 1, it means that you choose one element from l to r.
Also for n = 2 it is necessary to print the formula, any pair of integers is the geometrical progression, so for n = 2 the answer equals (r - l + 1)·(r - l), the first integer can be chosen by using r - l + 1 ways, the second which is not equal to the first by using r - l ways.
Possible asymptotic behavior:
$${ O ( { \sqrt [ n - 1 ] { r ^ { 2 } } } \cdot ( n + \log ^ { 3 } n ) ) }$$;
$$O\left( ^{n-1} \sqrt {r^{2}} \cdot (\log n + \log^{3} n) \right)$$ — when we make the binary transfer to the degree;
$${ O ( n \cdot { ^ { n - 1 } \sqrt { r } } + { ^ { n - 1 } \sqrt { r ^ { 2 } } } \cdot \log ^ { 3 } n ) }$$ — with preliminary count;
$${ \cal O } ( \log n \cdot { ^ { n - 1 } \sqrt { r } } + { ^ { n - 1 } \sqrt { r ^ { 2 } } } \cdot \log ^ { 3 } n )$$ — with binary preliminary count.