Рассмотрим числа
вида a ^ (a ^ (a ^ ...), где a – натуральное число, которое
появляется в записи два и больше раз, ^ - операция возведения в степень.
Назовем такие числа числицами (число + лестница). Например 27 = 3 ^ 3 и 16 = 2
^ (2 ^ 2) являются числицами. Число 1 также числица, так как 1 = 1 ^ 1. Найдите
количество числиц в промежутке от 1 до n включительно.
Вход. Одно число n (1 ≤ n ≤ 109).
Выход. Вывести
количество числиц, не превосходящих n.
|
Пример входа |
Пример выхода |
|
5 |
2 |
математика
Анализ алгоритма
Числицы очень
быстро растут, поэтому попробуем найти их всех, которые не превышают 109.
Ими являются: 1^1 = 1, 2^2 = 4,
2^(2^2) = 16, 2^(2^(2^2)) = 2^16 = 65536, 3^3, 4^4, …, 9^9 = 387420489.
Реализация алгоритма
Читаем значение n.
В переменной ans подсчитываем
количество числиц.
scanf("%d",&n);
int
ans = 0;
if
(n >= 1) ans++; // 1^1
if
(n >= 4) ans++; // 2^2
if
(n >= 16) ans++; // 2^(2^2)
if
(n >= 65536) ans++; // 2^(2^(2^2))
if
(n >= 3*3*3) ans++; // 3^3
if
(n >= 4*4*4*4) ans++; // 4^4
if
(n >= 5*5*5*5*5) ans++; // 5^5
if
(n >= 6*6*6*6*6*6) ans++; // 6^6
if
(n >= 7*7*7*7*7*7*7) ans++; // 7^7
if
(n >= 8*8*8*8*8*8*8*8) ans++; // 8^8
if
(n >= 9*9*9*9*9*9*9*9*9) ans++; // 9^9
Выводим ответ.
printf("%d\n",ans);