Задача
2¹⁵ = 32768, сумма цифр этого числа равна 3 + 2 + 7 + 6 + 8 = 26.
Какова сумма цифр числа 2¹⁰⁰⁰?
Решение
Первоначально мне казалось, что здесь как-то можно применить модульную арифметику. Определить последнюю цифру числа я смог, но вот дальше не задалось. Поэтому решил идти обычным путём и делать все необходимые вычисления вручную.
2 в степени 1000 это 2, удвоенная 999 раз.
Я беру начальное число 2 и складываю с самим собой, затем результат складываю с самим собой и т.д. Это очень длинное число (302 знака), и если представить задачу так: "сложите два числа длиной 302 знака", то получим практически идентичную задачу, которая уже решалась:
Только здесь даже проще.
Я резервирую массив длиной 340 байт под цифры числа. Я не знал заранее, что их будет 302, поэтому взял с некоторым запасом (примерно каждый третий разряд в степенях двойки даёт переполнение, поэтому 1000/3 будет 333).
Далее я просто делаю то, что и раньше – складываю число с самим собой в столбик. Но именно воспроизводить сложение двух чисел конечно нет необходимости, просто текущий разряд умножается на 2, и к нему прибавляется переполнение от предыдущего разряда.
Цифры расположены в массиве задом наперёд, т.е. младший разряд самый первый, но это не имеет значения, так как требуется только сумма цифр.
Ссылка на онлайн-компилятор языка C с текстом программы
Вся подборка задач: