0089. Relative Primes

Input file name:	relprim.in
Output file name:	relprim.out
Time limit:	3 s
Memory limit:	64 megabytes

Let us call some ordered set of N integer numbers nice if they don't have common divisors greater than one.

For two given integer numbers A and B find the number of nice sets that contain only numbers in range from A to B.

Input file

The input file contains three integer numbers: N, A and B (1 ≤ A ≤ B ≤ 10⁶, N ≤ 10, B^N ≤ 10¹⁸)

Output file

Output the answer to the task.

Examples:

relprim.in	relprim.out
2 1 2	3

Source: Petrozavodsk Winter 2003. Final Contest, Saturday, February 08

Discuss       Submit a solution



Printable version