Задача
Удивительно, но существуют только три числа, которые могут быть записаны в виде суммы четвёртых степеней их цифр:
1634 = 1^4 + 6^4 + 3^4 + 4^4
8208 = 8^4 + 2^4 + 0^4 + 8^4
9474 = 9^4 + 4^4 + 7^4 + 4^4
1 = 1^4 не считается, так как это - не сумма.
Сумма этих чисел равна 1634 + 8208 + 9474 = 19316.
Найдите сумму всех чисел, которые могут быть записаны в виде суммы пятых степеней их цифр.
Решение
На решение ушло бы буквально 2 минуты, если бы не одно "но". Нас просят найти ВСЕ числа, подходящие под условие, но откуда мы знаем, сколько их? До бесконечности проверять мы очевидно не сможем, значит должен быть какой-то предел, после которого условие точно никогда не будет выполняться.
Дли нахождения предела нужно проследить, как накапливаются разряды чисел и суммы степеней разрядов.
Возьмём максимальную цифру 9 и найдём, что 9^5 это 59049, то есть уже 5-значное число. Значит, предел уже содержит минимум 5 знаков. Далее найдём сумму пяти таких степеней и получим 295245, уже 6-значное число. Далее возьмём 6 и 7 знаков, и всё равно будем получать в сумме 6-значные числа. То есть сумма после 6 знаков становится заведомо меньше числа. Значит, предел будет равен (9^5)*6.
Вот до этого предела и устроим цикл, в котором будем банально раскладывать числа на цифры, вычислять суммы и сравнивать. Ничего особенного.
Программа работает быстро, но её можно ускорить ещё в три раза. Дело в том, что здесь используется функция pow() для возведения в степень. К сожалению, она работает не с целыми, а с вещественными числами. Целочисленная версия могла бы работать быстрее, но мы также можем заметить, что цифр всего 9, и степень вычисляется каждый раз для одних и тех же цифр. Вместо этого мы можем заранее вычислить 5-е степени цифр от 0 до 9 и сохранить их для повторного использования.
В результате программа отрабатывает быстрее в три раза, хотя на глаз отличить 15 миллисекунд от 46 миллисекунд будет сложно.
Ссылка на онлайн-компилятор языка C с текстом программы
Подборка всех задач: