Сумма цифр факториала
Это'это не домашнее задание. Я просто подумал, что кто-то может знать реальное решение этой проблемы.
Я был на соревновании по программированию еще в 2004 году, и была эта проблема:
По заданному n найдите сумму цифр n !. n может быть от 0 до 10000. Ограничение по времени: 1 секунда. Я думаю, что для каждого набора тестов было до 100 номеров.
Мое решение было довольно быстрым, но недостаточно быстрым, поэтому я просто позволил ему какое-то время работать. Он построил массив предварительно рассчитанных значений, которые я мог бы использовать в своем коде. Это был взлом, но это сработало.
Но был парень, который решил эту проблему с помощью примерно 10 строк кода, и он дал бы ответ в кратчайшие сроки. Я считаю, что это было какое-то динамическое программирование или что-то из теории чисел. Нам тогда было 16 лет, так что не должно быть "ракетостроение".
Кто-нибудь знает, какой алгоритм он мог бы использовать?
РЕДАКТИРОВАТЬ: Яизвините, если бы я неЯ прояснил вопрос. Как сказал mquander, должно быть умное решение, без ошибок, с простым кодом Pascal, парой циклов, O (n2) или что-то типа того. 1 секунда больше не является ограничением.
я нашелВот что если п> 5, то 9 делит сумму цифр факториала. Мы также можем найти сколько нулей в конце числа. Можем ли мы использовать это?
Хорошо, еще одна проблема из соревнований по программированию из России. Дано 1 <= N <= 2 000 000 000, выход N! мод (N + 1). Это как-то связано?