Skoro nie chcesz się już w to bawić, to trudno. Sam dokończę. Jeśli w moim rozwiązaniu zastąpimy nieszczęsną linię
ost *= k; przez
ost *= (k % 10);, to uzyskamy rozwiązanie zwracające poprawny wynik nawet dla
n=INT_MAX, ale szybkość takiego rozwiązania nie jest porywająca.
Spróbujmy rozwiązać analogiczne zadanie w systemie piątkowym. Żeby otrzymać liczbę
\(\displaystyle{ n!}\) bez końcowych zer w systemie piątkowym, wystarczy uciąć końcowe zera każdemu czynnikowi w iloczynie
\(\displaystyle{ 1\cdot2\cdot\ldots\cdot n,}\) bo
\(\displaystyle{ 5}\) jest liczbą pierwszą. Na przykład dla
\(\displaystyle{ n=113_5}\) mamy iloczyn:
\(\displaystyle{ 1_5\cdot2_5\cdot3_5\cdot4_5\cdot1{\gray{0}}_5\cdot\\
11_5\cdot12_5\cdot13_5\cdot14_5\cdot2{\gray{0}}_5\cdot\\
21_5\cdot22_5\cdot23_5\cdot24_5\cdot3{\gray{0}}_5\cdot\\
31_5\cdot32_5\cdot33_5\cdot34_5\cdot4{\gray{0}}_5\cdot\\
41_5\cdot42_5\cdot43_5\cdot44_5\cdot1{\gray{00}}_5\cdot\\
101_5\cdot102_5\cdot103_5\cdot104_5\cdot11{\gray{0}}_5\cdot\\
111_5\cdot112_5\cdot113_5.}\)
Z liczb w pierwszych czterech kolumnach dostaniemy
\(\displaystyle{ (1\cdot2\cdot3\cdot4)^6\cdot(1\cdot2\cdot3)}\) modulo
\(\displaystyle{ 5,}\) a z pozostałych po obcięciu jednego zera:
\(\displaystyle{ 1_5\cdot2_5\cdot3_5\cdot4_5\cdot1{\gray{0}}_5\cdot\\
11_5.}\)
Liczba
\(\displaystyle{ (1\cdot2\cdot3\cdot4)^p}\) przystaje do
\(\displaystyle{ 1}\) lub
\(\displaystyle{ 4}\) modulo
\(\displaystyle{ 5,}\) w zależności od parzystości
\(\displaystyle{ p.}\)
Mamy więc rozwiązanie w systemie piątkowym:
Kod: Zaznacz cały
int ostatnia5(int n) {
int wynik = 1;
while (n > 0) {
for (int k = n % 5; k > 1; k--) wynik *= k;
n /= 5;
if (n % 2) wynik *= 4;
wynik %= 5;
}
return wynik;
}
Zastanówmy się teraz, jak to się ma do rozwiązania wyjściowego problemu. Niech
\(\displaystyle{ p}\) i
\(\displaystyle{ q}\) oznaczają odpowiednio krotność liczby
\(\displaystyle{ 5}\) i
\(\displaystyle{ 2}\) w liczbie
\(\displaystyle{ n!}\) Znaleźliśmy ostatnią cyfrę piątkową takiego
\(\displaystyle{ x,}\) że
\(\displaystyle{ n!=5^p\cdot x.}\) Niech
\(\displaystyle{ y}\) będzie taką liczbą, że
\(\displaystyle{ n!=5^p\cdot2^q\cdot y=10^p\cdot(2^{q-p}\cdot y).}\) Mamy równość:
\(\displaystyle{ 2^{q-p}\cdot y = 2^{-p}\cdot x,}\)
co pozwala nam na znalezienie reszty z dzielenia przez
\(\displaystyle{ 5}\) liczby
\(\displaystyle{ 2^{q-p}\cdot y.}\) A reszta z dzielenia tej liczby przez
\(\displaystyle{ 2}\) na ogół jest równa
\(\displaystyle{ 0,}\) więc łatwo możemy znaleźć resztę z dzielenia przez
\(\displaystyle{ 10,}\) czyli odpowiedź do zadania.
Kod: Zaznacz cały
int krotnosc5(int n) {
int wynik = 0;
while (n /= 5) wynik += n;
return wynik;
}
int potegamod5(int k, int p) {
int wynik = 1;
p %= 4;
while (p-- > 0) wynik *= k;
return wynik;
}
int ostatnia(int n) {
if (n < 2) return 1;
else {
int wynik = ostatnia5(n) *
potegamod5(3,krotnosc5(n));
if (wynik % 2 != 0) wynik += 5;
return wynik % 10;
}
}
