Question

Найдите три последние цифры суммы 1 ^100 + 2^100 + · · · + 999^100 + 1000^100

Answer 1

Заметим, что число (10a + b)^100 дает такой же остаток при делении на 1000, что и b^100 (вспоминаем бином и начинаем раскладывать: слагаемые, содержащие 10a в степени 3 или больше точно делятся на 10^3, а остальные можно и выписать, получив (10a + b)^100 = b^100 + 100 * 10a * b^99 + 100 * 99 / 2 * (10a)^2 * b^98 + ...)

Итак, сумма дает такой же остаток от деления на 1000, что и 
(1^100 + 2^100 + ... + 10^100) * 100. Таким образом, нам нужно знать лишь последнюю цифру суммы 1^100 + 2^100 + ... + 9^100 (10^100 точно кончается на 0).

Задачу себе можно упростить, заметив, что x^100 кончается на ту же цифру, что и (10 - x)^100 [для обоснования тоже можно воспользоваться биномом]. Тогда последняя цифра такая же, что и у 2 * (1^100 + 2^100 + 3^100 + 4^100) + 5^100

1^100 кончается на 1
2^100 = ((2^5)^5)^4 кончается на то же, что и 2^4, т.е. на 6, т.к. 2^5 = 32 кончается на 2
3^100 = (3^4)^25 = 81^25 кончается на 1
4^100 = 2^200 = ((2^5)^5) кончается на то же, что 2^8 = 256, т.е. на 6
5^100 кончается на 5

Итого, последняя цифра такая же, что и у 2 * (1 + 6 + 1 + 6) + 5 = 33, т.е. 3
Тогда 100 * (...) кончается на 300.

ответ. 300.