Suma cyfr silni
To nie jest zadanie domowe. Właśnie pomyślałem, że ktoś może znać prawdziwe rozwiązanie tego problemu.
Byłem na konkursie programistycznym w 2004 roku i pojawił się ten problem:
Biorąc pod uwagę n, znajdź sumę cyfr n !. n może wynosić od 0 do 10000. Limit czasu: 1 sekunda. Myślę, że dla każdego zestawu testowego było do 100 numerów.
Moje rozwiązanie było dość szybkie, ale nie dość szybkie, więc po prostu pozwoliłem mu działać przez jakiś czas. Zbudował tablicę wstępnie obliczonych wartości, których mogłem użyć w moim kodzie. To był hack, ale zadziałało.
Ale był facet, który rozwiązał ten problem za pomocą około 10 linii kodu i dałby odpowiedź w mgnieniu oka. Uważam, że był to rodzaj dynamicznego programowania lub coś z teorii liczb. Mieliśmy wtedy 16 lat, więc nie powinno to być „nauką rakietową”.
Czy ktoś wie, jakiego rodzaju algorytmu mógłby użyć?
EDYTOWAĆ: Przepraszam, jeśli nie wyjaśniłem tego pytania. Jak powiedział mquander, powinno być sprytne rozwiązanie, bez bugnum, z prostym kodem Pascala, kilkoma pętlami, O (n2) czy jakoś tak. 1 sekunda nie jest już ograniczeniem.
znalazłemtutaj że jeśli n> 5, to 9 dzieli sumę cyfr silni. Możemy również znaleźć, ile zera znajduje się na końcu liczby. Czy możemy to wykorzystać?
Ok, kolejny problem z konkursu programistycznego z Rosji. Biorąc pod uwagę 1 <= N <= 2 000 000 000, wyjście N! mod (N + 1). Czy to w jakiś sposób powiązane?