Hỏi Về Chữ Số Tận Cùng Khác 0 Của N! - Programming - Dạy Nhau Học

Trang chủ » đếm Chữ Số 0 Tận Cùng Của N Giai Thừa » Hỏi Về Chữ Số Tận Cùng Khác 0 Của N! - Programming - Dạy Nhau Học

Có thể bạn quan tâm

(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 :slight_smile: (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 :smiley: ), 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 :smiley:

(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) :smiley: 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

Từ khóa » đếm Chữ Số 0 Tận Cùng Của N Giai Thừa