0089. Relative Primes

Имя входного файла:	relprim.in
Имя выходного файла:	relprim.out
Ограничение по времени:	3 s
Ограничение по памяти:	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

Источник: Petrozavodsk Winter 2003. Final Contest, Saturday, February 08

Обсудить       Отправить решение



Версия для печати