Chữ số cuối khác 0

Chữ số cuối khác 0

Đề thi Tin học Quốc gia Ireland, 1994.

Tìm chữ số cuối cùng khác 0 của n! với n trong khoảng 1..100.

Thí dụ:

-        n = 7, kết quả = 4.

-        n = 15, kết quả = 8.

Bài giải

Thuật giải của bạn Việt Hưng (Hà Tây, 2002) cho phép mở rộng giới hạn của n đến hàng chục vạn và nếu bạn muốn, có thể tiếp tục mở rộng đến hàng triệu.

Ý tưởng chính của Việt Hưng nằm ở công thức: 2 ´ 5 = 10 (hai lần năm là mười). Thật vậy, ta biết:

n! = 1.2.3...n

Các chữ số cuối cùng bằng 0 của n giai thừa được sinh ra khi và chỉ khi trong khai triển ra thừa số nguyên tố của tích trên có chứa các cặp thừa số 2 và 5. Vậy thì trước hết ta đếm số lượng các thừa số 2, kí hiệu là d2 và số lượng các thừa số 5, kí hiệu là d5.

Thí dụ, với n = 15 ta có dạng khai triển ra thừa số nguyên tố của n giai thừa như sau:

n! = 1.2.3.(2.2).5.(2.3).7.(2.2.2).9.(2.5).11. (2.2.3).13.(2.7).(3.5)

Do đó d2 = 11 và d5 = 3. Vậy ta có ba cặp 2.5 = 10 và số mũ dôi ra của thừa số 2 so với thừa số 5 sẽ là d2 – d5 = 11 – 3 = 8. Khi đó, kết quả sẽ là:

chữ số cuối cùng khác 0 của 15! = chữ số cuối cùng của k.2^d2-d5

Trong đó k là tích của các thừa số còn lại.

Dễ thấy với mọi n, ta luôn có d2 ³ d5 vì cứ hai số liên tiếp thì có một số chẵn (chia hết cho 2), còn năm số liên tiếp mới có một số chia hết cho 5.

Việc còn lại là lấy tích k của các số còn lại. Vì tích này không bao giờ tận cùng bằng 0 cho nên ta chỉ cần giữ lại một chữ số cuối cùng bằng cách lấy mod 10.

Để tính chữ số tận cùng của 2^m với m = d2 – d5 > 0 ta để ý đến tính tuần hoàn của nó, cụ thể là ta chỉ cần tính chữ số tận cùng của 2^{(m mod 4)} với các trường hợp:

m mod 4 = 0, 1, 2 và 3.

Theo thí dụ trên ta có m mod 4 = 8 mod 4 = 0, do đó chữ số cuối của 2^m là 6 chứ không phải là 1 vì m > 0. Ta tính được (những cặp 2 và 5 được gạch dưới)

15! = 1.2.3.4.5.6.7.8.9.10.11.12.13.14.15 =

         = 1.2.3.(2.2).5.(2.3).7.(2.2.2).9.(2.5).11. (2.2.3).13.(2.7).(3.5)

         Þ (3.3.7.9.11.3.13.7.3). 2⁸mod 10 =

                        = ((k mod 10) . (2⁸ mod 10)) mod 10 = (3.6) mod 10 = 8.

Chữ số cuối cùng khác 0 của 15! là 8.

Lưu ý rằng (a.b) mod m=((a mod m).(b mod m)) mod m cho nên ta có thể lấy mod ở các bước trung gian với số lần tùy ý.

Để tránh việc tràn số khi sử dụng các biến dung lượng nhỏ như kiểu word thay vì dùng longint chúng ta có thể tăng thêm một phép toán mod nữa. Chẳng hạn, khi tích luỹ kết quả, thay vì viết

k := (k*c) mod 10;

ta nên viết

k := (k*(c mod 10)) mod 10;

trong đó k là số có một chữ số, c là số có thể rất lớn, đủ để làm tích (k*c) vượt quá giới hạn cho phép. Thí dụ, nếu khai báo kiểu dữ liệu là word thì khi k = 8, c = 17999 ta có k*c = 8*17999 = 143992 > 65535 (giới hạn của word), trong khi 8 và 17999 đều nằm trong giới hạn cho phép.

Bình luận

Để ý rằng:

14! = 87178291200, có chữ số cuối cùng khác 0 là 2

15! = 1307674368000, có chữ số cuối cùng khác 0 là 8.

Nếu để tính 15! mà bạn chỉ lấy một chữ số cuối khác 0 của các phép tính trung gian thì sau khi tính chữ số cuối của 14! bạn sẽ nhận được 2 và cuối cùng là:

(2*15) mod 10 = 30 mod 10 = 3.

Kết quả này là sai vì chữ số cuối khác 0 của 15! là 8.

Chương trình sau đây chứa thủ tục find tìm chữ số cuối cùng khác 0 của n! với n trong khoảng 1..65535.

Ta thực hiện một cải tiến nhỏ như sau. Thay vì đếm số lượng các thừa số 2 (d2) và thừa số 5 (d5) sau đó làm phép trừ d2 – d5, ta đếm luôn một lần hiệu số này và ghi vào biến m. Cụ thể là với mỗi giá trị i = 2..n ta đếm số lượng các thừa số 2 trước, sau đó trừ đi số lượng các thừa số 5.

(*  Pascal  *)

(*---------------------------------------

 Tim chu so khac khong cuoi cung cua n!

----------------------------------------*)

uses crt;

function find(n: longint): longint;

var m: longint;

  {m – hieu so cac thua so 2 và thua so 5}

  i,k,c: longint;

begin {k – ket qua trung gian}

k :=  1; m := 0;        

find := k;

if (n <= 1) then exit;

d := 0;

for i := 2 to n do

         begin

c := i;

while c mod 2 = 0 do

            begin

m :=  m+1; c :=  c div 2;

            end;

while c mod 5 = 0 do

            begin

m :=  m-1; c :=  c div 5;

            end;

k := (k*(c mod 10)) mod 10;

          end;

case (m mod 4) of

0: c :=  6;

1: c :=  2;

2: c :=  4;

3: c :=  8;

end;

find := (k*c) mod 10;

end;

procedure run;

 var n: longint;

begin

writeln('--------------------');

repeat

write(' Nap N (Muon dung chuong trinh, bam 0 ): ');

read(n);

if n = 0 then halt;

writeln(' find(',n,') = ',find(n));

until false;

end;

BEGIN

run;

END.

Kĩ thuật gán trước

Bạn có thể thay lệnh Case trong việc tính chữ số tận cùng của 2^m bằng các thao tác sau:

1. Khai báo và gán trước trị cho mảng LuyThua

const LuyThua: array[0..3] of word = (6,2,4,8);

Ý nghĩa của dòng lệnh trên: khai báo một mảng kiểu word với bốn phần tử có chỉ số biến thiên từ 0..3 và gán trước trị cho mảng này là:

LuyThua[0] :=  = 6; {= 2⁴ mod 10}

LuyThua[1] = 2; {= 2¹ mod 10}

LuyThua[2] = 4; {= 2² mod 10}

LuyThua[3] = 8; {= 2³ mod 10}

Chú ý rằng, do đòi hỏi phải khai báo trước và gán đồng thời nên Turbo Pascal 7.0 quy định đặt khai báo này sau từ khoá const. Tuy nhiên LuyThua vẫn là biến mảng chứ không thể là hằng.

2. Khi cần tìm chữ số cuối cùng c của 2^m bạn khỏi phải dùng lệnh case, chỉ cần viết:

c  :=  LuyThua[m mod 4];

Hàm Find theo phương án mới sẽ như sau:

const LuyThua: array[0..3] of word = (6,2,4,8);

{-------------------------------------------}

Find – Tìm chữ số cuối cùng khác 0 của n!

Phuong an dung mang LuyThua gan truoc

--------------------------------------------}

function find(n: longint): longint;

var m: longint;

{m – hieu so cac thua so 2 và thua so 5}

i,k,c: longint; {k – ket qua trung gian}

begin

k :=  1; m := 0;

find := k;

if (n <= 1) then exit;

d := 0;

for i := 2 to n do

         begin

c := i;

while c mod 2 = 0 do

            begin

m  :=  m+1; c  :=  c div 2;

            end;

while c mod 5 = 0 do

            begin

m  :=  m-1; c  :=  c div 5;

            end;

k  := (k*(c mod 10)) mod 10;

          end;

 find  := (k*LuyThua[m mod 4]) mod 10;

end;