Сумма цифр факториала
Ссылка на оригинальную проблему
Это не домашнее задание. Я просто подумал, что кто-то может знать реальное решение этой проблемы.
Я был на соревновании по программированию еще в 2004 году, и была эта проблема:
По заданному n найдите сумму цифр n!. n может быть от 0 до 10000. Ограничение по времени: 1 секунда. Я думаю, что для каждого набора тестов было до 100 номеров.
Мое решение было довольно быстрым, но недостаточно быстрым, поэтому я просто позволил ему какое-то время работать. Он построил массив предварительно рассчитанных значений, которые я мог бы использовать в своем коде. Это был взлом, но это сработало.
Но был парень, который решил эту проблему с помощью примерно 10 строк кода, и он дал бы ответ в кратчайшие сроки. Я считаю, что это было какое-то динамическое программирование или что-то из теории чисел. В то время нам было 16 лет, поэтому это не должно быть "ракетостроение".
Кто-нибудь знает, какой алгоритм он мог бы использовать?
РЕДАКТИРОВАТЬ: Я извиняюсь, если я не разъяснил вопрос. Как сказал mquander, должно быть умное решение, без ошибок, с простым кодом Pascal, парой циклов, O (n2) или чем-то в этом роде. 1 секунда больше не является ограничением.
Я обнаружил здесь, что если n > 5, то 9 делит сумму цифр факториала. Мы также можем найти, сколько нулей в конце числа. Можем ли мы использовать это?
Хорошо, еще одна проблема из соревнований по программированию из России. Учитывая 1 <= N <= 2 000 000 000, выведите N! мод (N+1). Это как-то связано?
11 ответов
Я не уверен, кто все еще обращает внимание на эту тему, но здесь все равно идет.
Во-первых, в официальной связанной версии он должен быть только 1000 факториалов, а не 10000 факториалов. Кроме того, когда эта проблема была повторно использована в другом соревновании по программированию, ограничение по времени составило 3 секунды, а не 1 секунда. Это делает огромную разницу в том, как тяжело вам работать, чтобы получить достаточно быстрое решение.
Во-вторых, для фактических параметров конкурса решение Питера является надежным, но с одним дополнительным поворотом вы можете ускорить его в 5 раз с 32-битной архитектурой. (Или даже в 6 раз, если требуется только 1000!). А именно, вместо работы с отдельными цифрами, выполните умножение в базе 100000. Затем, в конце, суммируйте цифры в каждой суперразнице. Я не знаю, насколько хорош компьютер, на котором вы были допущены в конкурсе, но у меня дома есть рабочий стол, который примерно такой же старый, как и конкурс. Следующий пример кода занимает 16 миллисекунд на 1000! и 2,15 секунды за 10000! Код также игнорирует конечные 0, когда они появляются, но это экономит только около 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), где тильда означает, что вы можете добавить логарифмические факторы. У Карацубы есть простое ускорение, которое не уменьшает сложность времени, но все же улучшает его и может сэкономить еще 4 раза. Чтобы использовать его, вам также нужно разделить сам факториал на равные диапазоны размеров. Вы делаете рекурсивный алгоритм prod(k,n), который умножает числа от k до n на формулу псевдокода
prod(k,n) = prod(k,floor((k+n)/2))*prod(floor((k+n)/2)+1,n)
Затем вы используете Карацубу, чтобы сделать большое умножение, которое получается.
Даже лучше, чем Карацуба, алгоритм умножения Шонхаге-Штрассена на основе преобразования Фурье. Как это происходит, оба алгоритма являются частью современных библиотек большого числа. Быстрое вычисление огромных факториалов может быть важно для определенных приложений чистой математики. Я думаю, что Schonhage-Strassen излишне для соревнования по программированию. Карацуба действительно прост, и вы можете представить это в виде решения проблемы А +.
Часть поставленного вопроса - это некоторые предположения о том, что существует простой прием теории чисел, который полностью меняет проблему конкурса. Например, если вопрос должен был определить n! mod n+1, тогда теорема Уилсона говорит, что ответ равен -1, когда n + 1 простое, и очень легко увидеть, что это 2, когда n=3, а в противном случае 0, когда n + 1 является составным. Есть варианты этого тоже; например п! Также очень предсказуем мод 2n+1. Есть также некоторые связи между сравнениями и суммами цифр. Сумма цифр x mod 9 также равна x mod 9, поэтому сумма равна 0 mod 9, когда x = n! для n >= 6. Чередующаяся сумма цифр x mod 11 равна x mod 11.
Проблема в том, что если вам нужна сумма цифр большого числа, а не по модулю, уловки из теории чисел заканчиваются довольно быстро. Сложение цифр числа плохо сочетается с сложением и умножением с переносами. Часто трудно пообещать, что математика не существует для быстрого алгоритма, но в этом случае я не думаю, что существует какая-либо известная формула. Например, держу пари, что никто не знает сумму цифр факториала гугола, хотя это просто какое-то число с примерно 100 цифрами.
Это A004152 в онлайн-энциклопедии целочисленных последовательностей. К сожалению, у него нет никаких полезных советов о том, как его эффективно рассчитать - его рецепты клен и математика используют наивный подход.
Я бы атаковал вторую задачу, чтобы вычислить N! mod (N+1), используя теорему Вильсона. Это сводит проблему к проверке, является ли N простым.
Небольшой, быстрый скрипт на python, найденный по адресу http://www.penjuinlabs.com/blog/?p=44. Это элегантно, но все еще грубой силой.
import sys
for arg in sys.argv[1:]:
print reduce( lambda x,y: int(x)+int(y),
str( reduce( lambda x, y: x*y, range(1,int(arg)))))
$ time python sumoffactorialdigits.py 432 951 5436 606 14 9520
3798
9639
74484
5742
27
141651
real 0m1.252s
user 0m1.108s
sys 0m0.062s
Предположим, у вас большие числа (это наименьшая из ваших проблем, если предположить, что N действительно большое, а не 10000), и давайте продолжим.
Хитрость ниже в том, чтобы фактор N! путем факторинга всех n<=N, а затем вычислить степени факторов.
Иметь вектор счетчиков; один счетчик для каждого простого числа до N; установите их равными 0. Для каждого n<= N разложите множитель n и соответственно увеличьте счетчики простых множителей (умело делайте множители: начните с маленьких простых чисел, постройте простые числа при разложении и помните, что деление на 2 - это сдвиг). Вычтите счетчик 5 из счетчика 2 и сделайте счетчик 5 нулем (здесь никого не волнуют факторы 10).
вычислить все простые числа до N, выполнить следующий цикл
for (j = 0; j< last_prime; ++j) {
count[j] = 0;
for (i = N/ primes[j]; i; i /= primes[j])
count[j] += i;
}
Обратите внимание, что в предыдущем блоке мы использовали только (очень) маленькие числа.
Для каждого простого множителя P вы должны вычислить P до степени соответствующего счетчика, который занимает лог (счетчик) времени с использованием итеративного возведения в квадрат; Теперь вы должны умножить все эти степени простых чисел.
В целом у вас есть около N log(N) операций с небольшими числами (log N простых факторов) и Log N Log(Log N) операций с большими числами.
и после улучшения в редактировании, только N операций с небольшими числами.
НТН
1 секунда? Почему ты не можешь просто вычислить n! и сложить цифры? Это 10000 умножений и не более нескольких десятков тысяч сложений, что должно занимать примерно одну миллиардную долю секунды.
Вы должны вычислить фаткориал.
1 * 2 * 3 * 4 * 5 = 120.
Если вы хотите вычислить только сумму цифр, вы можете игнорировать конечные нули.
На 6! Вы можете сделать 12 х 6 = 72 вместо 120 * 6
За 7! Вы можете использовать (72 * 7) MOD 10
РЕДАКТИРОВАТЬ.
Я написал ответ слишком быстро...
10 является результатом двух простых чисел 2 и 5.
Каждый раз, когда у вас есть эти 2 фактора, вы можете игнорировать их.
1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11 * 12 * 13 * 14 * 15...
1 2 3 2 5 2 7 2 3 2 11 2 13 2 3
2 3 2 3 5 2 7 5
2 3
Коэффициент 5 появляется на 5, 10, 15...
Тогда конечный ноль появится после умножения на 5, 10, 15...
У нас много 2 и 3... Мы скоро переполнимся:-(
Тогда вам все еще нужна библиотека для больших чисел.
Я заслуживаю быть пониженным!
Посмотрим. Мы знаем, что расчет n! для любого достаточно большого числа в конечном итоге получится число с множеством конечных нулей, которые не влияют на сумму. Как насчет отсечки нуля по пути? Что бы сохранить размер числа немного меньше?
Хм. Нету. Я только что проверил, и целочисленное переполнение все еще большая проблема даже тогда...
Даже без целых чисел произвольной точности это должно быть перебором. В формулировке проблемы, с которой вы связаны, самый большой факториал, который нужно будет вычислить, будет 1000!. Это число с 2500 цифрами. Так что просто сделайте это:
- Выделите массив из 3000 байтов, каждый из которых представляет одну цифру в факториале. Начните со значения 1.
- Выполните умножение начальной школы на массиве многократно, чтобы вычислить факториал.
- Суммируйте цифры.
Выполнение повторных умножений является единственным потенциально медленным шагом, но я уверен, что 1000 умножений могут быть выполнены за секунду, что является наихудшим случаем. Если нет, вы можете заранее вычислить несколько "веховых" значений и просто вставить их в свою программу.
Одна потенциальная оптимизация: устранение конечных нулей из массива при их появлении. Они не повлияют на ответ.
ОБЩЕЕ ЗАМЕЧАНИЕ: Я использую подход соревнования по программированию. Вы, вероятно, никогда не будете делать это в профессиональной работе.
from math import factorial
def f(x):
return sum(list(map(int, str(factorial(x)))))
print(int(input("Enter interger for sum of digits in its factorial: ")))
Другое решение с использованием BigInteger
static long q20(){
long sum = 0;
String factorial = factorial(new BigInteger("100")).toString();
for(int i=0;i<factorial.length();i++){
sum += Long.parseLong(factorial.charAt(i)+"");
}
return sum;
}
static BigInteger factorial(BigInteger n){
BigInteger one = new BigInteger("1");
if(n.equals(one)) return one;
return n.multiply(factorial(n.subtract(one)));
}