E mới học c++ đề hỏi tìm chữ số khác 0 tận cùng của n! N <1000000000 nhập từ bàn phím
Ai giúp e đk k ạ
Hỏi về chữ số tận cùng khác 0 của n!
Bỏ đk r xg sao nữa ah
b đọc thử cái này xem có giúp được gì k
https://sites.google.com/a/alo0781.com/qvluom/tai-lieu-va-bai-viet/thuat-toan-tim-chu-so-tan-cung-khac-0-cua-n-giai-thua
Những bài kiểu này nó liên quan tới thuật toán nhiều hơn là liên quan tới lập trình.
4 Likes
(theo qvluom - link trên)
Một thừa số 5 sẽ triệt tiêu đúng một thừa số 2 vì 2 * 5 = 10 và 1 là phần tử trung hòa.
Ý tưởng cơ bản vẫn là đẩy hết thừa số 2 và 5 ra một bên, ở đây nhóm từ 0 đến 9, rồi tính 2*3*4*6*7*8*9 = 72576, nên chỉ cần chọn 16 = 2^4 thôi 
(1)
Tích của pt trong 5ℤ = 5 * 10 * 15 * 20 * ... * 5k = 5 * 1 * 5 * 2 * 5 * 3 * ... * 5 * k = 5^k* (1 * 2 * 3 * ... * n) = 5^k * k!
Vậy [1…10] mang 2 thừa số 5 và 4 thừa số 2 (2^4) (thừa số 2 của 10 nằm trong k! rồi 
), triệt tiêu còn 2 thừa số 2 = 4, hay
f(10k' + r) = (4^k' mod 10 * f(2*k' + (r>=5 ? 1:0)) * table[r]) mod 10
4^k’ mod 10 là phép tính O(1) vì nó bằng 6 - (k’ & 1) << 2.
Vẫn còn một dấu chấm hỏi là [5…9] thì nếu không lấy 2k’ + 1 thì kết quả sai. Lí do là vì table[5] = 2 thì chỉ mới nhân 5 thôi, còn 2k’ + 1 nữa
(1) Gọi @(n) là chữ số tận cùng của n khác 0 thì @(n) := n%10 == 0 ? @(n/10) : n%10. Vậy @(ab) = @(@(a) * @(b)) (mod 10). Mà 576 = 16 (mod 10) nên thay vào thôi. Đặt @(n!) = f(n).
Thêm một bước nữa ta sẽ thấy 1*2*3*4 = 4 (mod 10), vậy còn một thừa số 2.
6*7*8*9 = 4 (mod 10), như trên.
Nhìn vào sẽ nghĩ đến giản hóa f(5k+r) = (2^k mod 10 * f(k) * table[r]) mod 10. Tuy nhiên sẽ sai trong [5…9]. Vì vậy table phải là 10 slot, hay table[(k mod 2) * 5 + r] với table[0..9] = {1, 1, 2, 6, 4, 2, 2, 4, 2, 8}. f(10) = 2^2 mod 10 * f(2) * table[0] = 4 * table[2] * 1 = 8 đúng. Về tính toán thì công thức phía trên tuy xấu nhưng tính nhanh hơn công thức dưới này.
nếu n < 10 thì f(n) = table[n]
CT1: f(10k + r) = (k mod 2 ? 4:6) * f(2*k + r>=5 ? 1:0) * table[r]) mod 10
CT2: f(5k + r) = ({6, 2, 4, 8}[k mod 4] * f(k) * table[r + k mod 2 ? 5:0]) mod 10
5 Likes
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?