Факториалын сүүлийн тэг биш цифр

Өгсөн n натурал тооны факториалын хамгийн арын тэг биш цифрийг ол.
Жишээ 1:
Оролт: 5
Гаралт: 2 // 5!=120 -> 2
Жишээ 2:
Оролт: 1000000
Гаралт: 4
Эх өгүүлбэр: [Факториал 2]
Энэ бодлогын тухай дахь өөрийнхөө мэдэж байгаа хамгийн сайн алгоритмаа танилцуулъя.
N=1 үед л хариу сондгой тоо гарна. Иймд N=1 үед хариу:1. Харин бусад тохиолдолд нь:
1. 1*2*3*4*6*7*8*9 (5 болон 0-г орхисон) үржвэрийг сонирхвол сүүлийн тэг биш цифр нь 6 байгаа. Энэ бол бодлогын маань гол түлхүүр.
2. 6-г ямар ч тэгш цифрээр үржүүлсэн тэр тэгш цифрээр нь төгссөн тоо гардаг.

N0 = N - (N MOD 10) гэж тэмдэглэе (тооны сүүлийн цифрийг тэг болгосон гэсэн үг)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 ... N0
гэсэн дараалын 10-т болгон дахь (1, 2, 3, 4, 6, 7, 8, 9) гэсэн цифрүүдээр төгссөн тоонууд нь 6-гаар төгсөх учир (2) - ээс үндэслэн эдгээрийг орхичихож болно.
Тэгэхлээр дараах тоонууд үлдэнэ:
5 10 15 20 25 30 35 40 45 ... N0 N0+1 ... N
Ингээд N0 болон түүнээс өмнөх тоонуудыг 5-д хуваачихвал 1 2 3 4 5 ... гэх мэт цуваа үүснэ...
Тэгэхлээр бүдүүн тоймоор бол:
F(n) = ( 5^(n/5) * F(n/5) * (N0+1 * ... * N) тооны сүүлийн тэг биш цифр) гэсэн рекурсив гарна.

Тэгээд 5^k гэсэн илэрхийлэл нь тооцоог хүндрүүлэх тул:2^n зэргийг үржүүлээд хуваагаад өгчихвөл 10^k/2^k зэрэг болох ба энэ нь 16/2=8 байдагаас *6/2=8 (сондгой тоог тооцохгүй!) гэж үзэж болно. Иймэд 5^k => 10^k / 2^k => 8^k гэж болно. Мөн 8^(k+4) = 8^k * 4096 гэдгээс
8^(k+4) mod 10 = 8^k mod 10 гэж гарна.

Иймд
F(n) = 8^(n/5 mod 4) * F(n/5) * (N0+1 * ... * N); гэсэн рекурсив гарах ба энэ нь бодолтонд хангалттай.
N0+1 -ээс N хүртэл (N mod 10) тоо байгаа учраас (N0+1 * ... * N) илэрхийллийг яаж л бол яаж хялбарчилж болно.
Жишээ бодолт:
n = 123 үед
123! == 5^14 * 14! * (121 * 122 * 123) == 8^14 * 14! * 6 == 14! * 4;
4*14! == 4 * 5^2 * 2! * (11*12*13*14) == 4 * 8^2 * 2 * 4 == 6;

Алгоритмийн шинжилгээ: O(log5(N))