Я не уверен, кто все еще обращает внимание на эту тему, но здесь все равно.
Во-первых, в официальной связанной версии он должен быть 1000 факториалов, а не 10000 факториалов. Кроме того, когда эта проблема была повторно использована в другом конкурсе по программированию, ограничение времени составляло 3 секунды, а не 1 секунду. Это имеет огромное значение в том, как сложно работать, чтобы получить достаточно быстрое решение.
Во-вторых, для реальных параметров конкурса решение Питера звучит, но с одним дополнительным поворотом вы можете ускорить его в 5 раз с 32-битной архитектурой. (Или даже коэффициент 6, если требуется только 1000!) А именно, вместо того, чтобы работать с отдельными цифрами, реализуйте умножение в базе 100000. Затем в конце суммируйте цифры в каждой суперзнаке. Я не знаю, насколько хорош компьютер, которого вы разрешили в конкурсе, но у меня есть настольный компьютер дома, который примерно такой же старый, как и конкурс. Следующий пример кода составляет 16 миллисекунд за 1000! и 2,15 секунды для 10000! Код также игнорирует завершающие 0s по мере их появления, но это экономит около 7% работы.
#include <stdio.h>
int main() {
unsigned int dig[10000], first=0, last=0, carry, n, x, sum=0;
dig[0] = 1;
for(n=2; n <= 9999; n++) {
carry = 0;
for(x=first; x <= last; x++) {
carry = dig[x]*n + carry;
dig[x] = carry%100000;
if(x == first && !(carry%100000)) first++;
carry /= 100000; }
if(carry) dig[++last] = carry; }
for(x=first; x <= last; x++)
sum += dig[x]%10 + (dig[x]/10)%10 + (dig[x]/100)%10 + (dig[x]/1000)%10
+ (dig[x]/10000)%10;
printf("Sum: %d\n",sum); }
В-третьих, существует удивительный и довольно простой способ ускорить вычисление с помощью другого значимого фактора. При использовании современных методов умножения больших чисел для вычисления n! Не требуется квадратичное время. Вместо этого вы можете сделать это в O-тильде (n), где тильда означает, что вы можете бросить логарифмические факторы. Существует простое ускорение due to Karatsuba, которое не привносит сложную временную сложность, но все же улучшает его и может сэкономить еще один коэффициент 4 или около того. Чтобы использовать его, вам также необходимо разделить факториал на равные диапазоны. Вы делаете рекурсивный алгоритм тычок (k, n), которая умножает число от к до п по формуле псевдокода
prod(k,n) = prod(k,floor((k+n)/2))*prod(floor((k+n)/2)+1,n)
Затем вы используете Карацуб, чтобы сделать большой размножению, что приводит.
Даже лучше, чем Карацуба, является алгоритмом умножения Шонхаге-Штрассена на основе Фурье. Как это бывает, оба алгоритма являются частью современных библиотек большого числа. Вычисление огромных факториалов быстро может быть важным для некоторых приложений чистой математики. Я думаю, что Шонхаге-Штрассен слишком много для конкурса на программирование.Карацуба действительно прост, и вы можете себе это представить в решении A + проблемы.
Часть вопроса представляет собой некоторые предположения о том, что существует простая теория чисел, которая полностью изменяет проблему конкурса. Например, если бы вопрос заключался в определении n! mod n + 1, то теорема Уилсона гласит, что ответ -1, когда n + 1 является простым, и очень просто понять, что он равен 2 при n = 3 и в противном случае 0, когда n + 1 является составным. Есть и вариации этого; например, n! также является весьма предсказуемым mod 2n + 1. Существуют также некоторые связи между конгруэнциями и суммами цифр. Сумма цифр x mod 9 также равна x mod 9, поэтому сумма равна 0 mod 9 при x = n! при n> = 6. Переменная сумма цифр x mod 11 равна x mod 11.
Проблема в том, что если вы хотите, чтобы сумма цифр большого количества, а не всего по модулю, трюки из числа теория заканчивается довольно быстро. Добавление цифр числа не очень хорошо связано с добавлением и умножением на переносы. Часто трудно пообещать, что математика не существует для быстрого алгоритма, но в этом случае я не думаю, что существует какая-либо известная формула. Например, я уверен, что никто не знает сумму цифр факториала googol, хотя это всего лишь несколько цифр с примерно 100 цифрами.
Вы уверены, что это не был повторен сумма цифр, как 88 -> 8 + 8 = 16 -> 7? Я могу сделать это в 10 строках кода. – tom10
@ tom10: Это вряд ли будет вопросом; так как решение было бы просто «если n> = 6 вернет 9, а еще вернет n-й элемент (1, 2, 6, 6, 3)». Это потребует менее 10 строк кода. :-) – ShreevatsaR
@ShrevatsaR, и все остальные: да, да, я понимаю, что моя перефразировка делает этот вопрос довольно простым для большинства в этом списке, но это не плохой вопрос для 16-летнего. И учитывая, что он сидит здесь на SO без ответа в течение нескольких часов ... действительно ли исходное заявление кажется разумным? Или это Тест Путнам компьютерных наук? – tom10