Ограничения: время – 200ms/500ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Будем называть натуральное число красивым, если сумма квадратов его цифр является полным квадратом.
Например, число 34 является красивым, так как `3^2+4^2=25=5^2`, а число 123 не является красивым, так как `1^2+2^2+3^2=14`.
Первая строка ввода содержит одно целое число `N` (`1 <= N <= 10^{18}`).
Вывести одно целое число — количество красивых чисел в диапазоне от 1 до `N` включительно.
```sample Пример ввода
50
```
```sample Пример вывода
16
```
Красивыми будут следующие числа 1,2,3,4,5,6,7,8,9,10,20,30,34,40,43,50.
*Система оценки и описание подзадач*
||.u|Подзадача 1 (50 баллов)||
`1 <= N <= 10^5`.
В этой подзадаче 5 тестов, каждый тест оценивается в 10 баллов. Баллы за каждый тест начисляются независимо.
||.u|Подзадача 2 (30 баллов)||
`N=10^k`, где `6 <= k <= 18.`
Необходимые подзадачи: 1.
В этой подзадаче 6 тестов. Баллы за подзадачу начисляются только в случае, если все тесты для этой подзадачи успешно пройдены.
||.u|Подзадача 3 (20 баллов)||
`10^5 <= N <= 10^{18}`
Необходимые подзадачи: 1, 2.
В этой подзадаче 4 теста. Баллы за подзадачу начисляются только в случае, если все тесты для этой подзадачи успешно пройдены.
По запросу сообщается результат окончательной проверки на каждом тесте в подзадаче 1, и о первой ошибке в подзадачах 2 и 3.
Начало
Рабочее место участника
Динамическое программирование и запоминающие функции