Link to the original problem

Ödev konusu değil. Ben birisi bu sorun için gerçek bir çözüm olduğunu düşündük.

Programlama Yarışması 2004, ve bu sorun vardı yine.

Verilen n, n basamak toplamı. n 10000 0 olabilir. Zaman sınırı: 1 saniye. Her bir deney seti için 100'e kadar sayılar vardı sanırım.

Benim çözüm oldukça hızlı ama yeterince hızlı değildim, ben sadece bir süre için bırakın. Benim kod benim işime yarar önceden hesaplanmış değerlerin bir dizi yaptı. Bir hack oldu, ama işe yaradı.

Ama kod 10 satır ile bu sorunu çözen bir adam vardı ve hiçbir zaman bir cevap verecek. Dinamik programlama bir tür olduğuna inanıyorum, ya da sayı teorisi bir şey. Bir olmamalı o zaman 16 yaşındaydık "roket bilimi".

Herkes kullanabilir biliyor mu?

EDİT: Eğer soru açık ifade etmedim eğer doğru değilse özür dilerim. Mquander, zekice bir çözüm olması gerektiğini söyledi, bugnum olmadan, sadece düz Pascal kodu, döngüler, (n . O çift gibi ^sup>2) ya da onun gibi bir şey. 1 saniye kısıtlaması değil artık.

N ^ here buldum . 5, 9, sonra böler bir faktöriyel basamak toplamı. Biz de pek çok sıfır var nasıl numarasını sonunda bulabilirsiniz. Bunu kullanabilir miyiz?

Tamam, Rusya'dan programlama yarışmasından başka bir sorun. 1 <= verilen&;= 2 000 000 000, çıkış N lt N! mod (N 1). Bir şekilde ilişkili mi?

Yine de bu konuya dikkat, ama burada zaten kim gider emin değilim.

İlk olarak, resmi görünüşlü bağlantılı sürümünde, sadece 1000 faktöriyel, değil 10000 faktöriyel olmalı. Bu sorun, başka bir programlama Yarışması yeniden, ne de, zaman sınırı 3 saniye, 1 saniye. Bu ne kadar zor çalışmak zorunda büyük bir fark yeterince hızlı bir çözüm elde etmek için yapar.

İkinci olarak, yarışma gerçek parametreleri, Peter çözüm geliyor ama ekstra bir bükülme ile 32-bit mimarisi ile 5 kat hızlı olur. (Veya sadece 1000 eğer 6 kat bile! arzu edilir.) Yani, tek haneli ile çalışmak yerine, temel 100000 çarpma uygulamak. O zaman sonunda, süper-hane içinde her hane toplam. Ne kadar iyi bir bilgisayar yarışmasına izin verildi bilmiyorum, ama yarışma olarak yaklaşık olarak eski evde bir masaüstü var. Aşağıdaki örnek kodu 1000 için 16 milisaniye! ve 10000 için 2.15 saniye! Kodu da büyümek 0s izleyen yok sayar, ama bu işi yalnızca %7 kazandırıyor.

#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] = carry0000;
            if(x == first && !(carry0000)) first  ;
            carry /= 100000; }
        if(carry) dig[  last] = carry; }
    for(x=first; x <= last; x  )
        sum  = dig[x]   (dig[x]/10)   (dig[x]/100)   (dig[x]/1000)
              (dig[x]/10000);
    printf("Sum: %d\n",sum); }

Üçüncü olarak, başka bir büyük faktör ile hesaplama hızlandırmak için harika ve oldukça basit bir yolu var. Çok sayıda çoğalarak için modern yöntemler ile, n hesaplamak için ikinci dereceden zaman! almaz. Bunun yerine, tilde logaritmik faktörler atmak anlamına gelir nerede O-tilde(n) zaman, bunu yapabilirsiniz. Bu zaman karmaşıklığını getirmiyor, ama yine de geliştiren basit bir hızlanma due to Karatsuba ve 4 veya başka bir faktör kurtarabilir. Bunu kullanmak için, sen de kendi içine eşit aralıklar ölçekli faktöriyel bölmek gerekir. Özyinelemeli bir algoritma k sayıları çarpar prod(k,n) aşağıdaki formüle göre n

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

Sonra Karatsuba büyük çarpma sonuçlar yapmak için kullanın.

Karatsuba bile daha iyi olduğunu Fourier dönüşümü tabanlı Schonhage-Luxembourg çarpma algoritması. Böyle olduğundan, her iki algoritmaları modern büyük sayı kütüphaneler parçası. Hızlı bir şekilde büyük faktöriyel hesaplama bazı saf matematik uygulamaları için önemli olabilir. Schonhage-Luxembourg programlama Yarışması için overkill olduğunu düşünüyorum. Karatsuba gerçekten basittir ve bu soruna bir çözüm olarak düşünebiliriz.

Poz bölümü tamamen Yarışması sorunu değiştiren basit bir sayı teorisi hile var bazı spekülasyonlar. Eğer soru n belirlemek için olsaydı örneğin,! mod n 1, Wilson teoremi diyor cevap -1 n 1 Başbakan, ve gerçekten kolay egzersiz için değil 2, n=3 ve aksi halde 0 n 1 kompozit. Bu çeşitleri de vardır; örneğin n! ayrıca 2n 1 mod çok tahmin edilebilir. Ayrıca eşlenik ve basamak toplamları arasında bazı bağlantılar var. X mod 9 da toplamıdır ediliyor 9, mod x in rakamları toplamı 0 mod 9 x = n! n ^ için . = 6. X mod 11 mod x eşittir 11 rakamını alternatif toplamıdır.

Sorun ise çok sayıda modül bir şey değil, rakamları toplamı istiyorsanız, sayılar kuramı hileler çok çabuk tükendi. Bir sayının basamak eklemek de ayrıca ve taşıyan ile çarpma ile örgü yok. Genellikle zor matematik hızlı bir algoritma yok böyle bir söz, ancak bu durumda bilinen herhangi bir formül olduğunu sanmıyorum. Örneğin, sadece yaklaşık 100 haneli bir numara olmasına rağmen hiç kimse onun yüzüncü kuvveti bir faktör bu rakamları toplamı bilir eminim.