Сумма цифр факториала

Ответ 1

Я не уверен, кто все еще обращает внимание на эту тему, но здесь все равно.

Во-первых, в официальной связанной версии он должен быть только 1000 факториальных, а не 10000 факториалов. Кроме того, когда эта проблема была повторно использована в другом конкурсе по программированию, ограничение времени составляло 3 секунды, а не 1 секунду. Это сильно влияет на то, как сложно работать, чтобы получить достаточно быстрое решение.

Во-вторых, для реальных параметров конкурса, решение Peter звучит, но с одним дополнительным завихрением вы можете ускорить его в 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), где тильда означает, что вы можете бросить логарифмические факторы. Существует простое ускорение из-за Карацубы, которое не приносит временной сложности до этого, но все же улучшает его и может сэкономить еще один фактор 4 или так. Чтобы использовать его, вам также необходимо разделить факториал на равные диапазоны. Вы создаете рекурсивный алгоритм prod (k, n), который умножает числа от k на n по формуле псевдокода

prod(k,n) = prod(k,floor((k+n)/2))*prod(floor((k+n)/2)+1,n)

Затем вы используете Karatsuba для выполнения большого умножения.

Даже лучше, чем Карацуба - это алгоритм умножения Шонхаге-Штрассена на основе Фурье-преобразования. Как это бывает, оба алгоритма являются частью современных библиотек большого числа. Вычисление огромных факториалов быстро может быть важным для некоторых приложений чистой математики. Я думаю, что Шонхаге-Штрассен слишком много для конкурса на программирование. Karatsuba действительно прост, и вы можете представить это в решении 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 цифрами.

Ответ 2

Это A004152 в Онлайн-энциклопедия Integer Последовательности. К сожалению, у него нет полезных советов о том, как правильно его вычислять - его рецепты клена и математики принимают наивный подход.

Ответ 3

Я бы атаковал вторую проблему, чтобы вычислить N! mod (N + 1), используя теорему Вильсона. Это уменьшает проблему до проверки того, является ли N простым.

Ответ 4

Маленький быстрый python script найден в 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

Ответ 5

Предположим, что у вас большие числа (это наименьшая из ваших проблем, если предположить, что 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) операции с большими числами.

Edit

и после улучшения редактирования, только N операций на небольших числах.

конец редактирования

НТН

Ответ 6

1 секунда? Почему вы не можете просто вычислить n! и добавить цифры? Это 10000 умножений и не более нескольких десятков тысяч дополнений, которые должны занимать примерно одну миллионную долю секунды.

Ответ 7

Посмотрим. Мы знаем, что вычисление n! для любого достаточно большого количества в конечном итоге приведет к числу с большим количеством конечных нулей, которые не вносят вклад в сумму. Как насчет сбрасывания нулей по пути? Это позволит немного уменьшить размер элемента?

Хм. Неа. Я просто проверил, и целочисленное переполнение все еще большая проблема даже тогда...

Ответ 8

Вы должны вычислить жир.

1 * 2 * 3 * 4 * 5 = 120.

Если вы хотите только вычислить сумму цифр, вы можете игнорировать конечные нули.

Для 6! вы можете сделать 12 x 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...

У нас много двух и трех... Мы скоро переполним: - (

Затем вам по-прежнему нужна библиотека для больших чисел.

Я заслуживаю того, чтобы его нивелировали!

Ответ 9

Даже без целых чисел произвольной точности это должно быть грубым. В заявлении проблемы, с которым вы связались, самый большой фактор, который нужно будет вычислить, будет 1000!. Это число с примерно 2500 цифрами. Так просто сделайте это:

• Выделить массив из 3000 байтов, причем каждый байт представляет одну цифру в факториале. Начните со значения 1.
• Повторное умножение класса школы на массив, чтобы вычислить факториал.
• Составьте цифры.

Выполнение повторных умножений является единственным потенциально медленным шагом, но я уверен, что 1000 умножений могут быть выполнены за секунду, что является наихудшим случаем. Если нет, вы можете заранее вычислить несколько значений "вехи" и просто вставить их в свою программу.

Одна потенциальная оптимизация: Исключите конечные нули из массива, когда они появляются. Они не повлияют на ответ.

ОБЫЧНОЕ ПРИМЕЧАНИЕ: Я беру подход к программированию и конкуренции. Вы, вероятно, никогда не сделаете этого в профессиональной работе.

Ответ 10

другое решение с использованием 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)));
}