Cái bài 2 của Mr_invicible đã được đề cập trong số 6 năm 2004 báo Tin học và nhà trường,mong các bạn tham khảo thêm.
Thuật toán{lấy của người khác,ko phải em}
Đầu tiên ta cần biết công thức Lagrange như sau:
x=[N / p] + [N / p^2] + [N / p^3] + ... + [N / p^k]
với p là số nguyên tố, [] là dấu phần nguyên, x là số mũ của p nếu phân tích n! ra thừa số nguyên tố. k là số thoả p^k<=N
Thứ 2, ta có nhận xét nếu phân tích ra thừa số nguyên tố thì số mũ của 2 luôn lớn hơn của 5 (cái này có thể dùng định lý trên chứng minh hoặc thừa nhận cũng được)
Ta lại có n!=n*(n-1)!
==> L(n!)=L(L(n).L((n -1)!)) với n không chia hết cho 5
(với hàm L(x) cho giá trị là chữ số tận cùng khác 0 của x);
Từ đó ==> nếu ta biết được L((5n)!) thì ta sẽ biết được L((5n+j)!) với j=0,1,2,3,4;
Một chứng minh tương tự nếu ta có L((25n)!) thì ta sẽ biết được L((25n+5j)!)
Và tổng quát ta sẽ tính được L((n*5^k+j*5^(k-1))!) theo L((n*5^k)!)
Còn nếu bạn nào cần code bài đó thì tui sẵn lòng,1 tỉ vẫn thỏa mãn yêu cầu bài toán{thực ra code của mình khá dài,lấy code của người khác,xin mấy bạn thông cảm,học hành chưa thành}
Code:
const b1:array[1..4] of integer =(2,4,8,6);
var n:longint;
a:array[0..9] of longint;
f:array[1..9,1..9] of longint;
ff:array[1..9] of longint;
Procedure tinhtong(n:longint);
var tg,i:longint;
begin
tg:=n div 10;
for i:=1 to 9 do
a[i]:=a[i]+tg;
for i:=tg*10 to n do
inc(a[i mod 10]);
end;
Procedure init;
begin
fillchar(f,sizeof(f),0);
f[2,1]:=2; f[2,2]:=4; f[2,3]:=8; f[2,4]:=6;
f[3,1]:=3; f[3,2]:=9; f[3,3]:=7; f[3,4]:=1;
f[4,1]:=4; f[4,2]:=6;
f[6,1]:=6;
f[7,1]:=7; f[7,2]:=9; f[7,3]:=3; f[7,4]:=1;
f[8,1]:=8; f[8,2]:=4; f[8,3]:=2; f[8,4]:=6;
f[9,1]:=9; f[9,2]:=1;
ff[2]:=4; ff[3]:=4; ff[4]:=2; ff[6]:=1;
ff[7]:=4; ff[8]:=4; ff[9]:=2;
ff[5]:=1; ff[1]:=1;
end;
Function lui(x1,d1:longint):integer;
var k1:Integer;
begin
case x1 of
2: k1:=1;
4: k1:=2;
8: k1:=3;
6: k1:=4;
end;
d1:=d1 mod 4;
{lui di d buoc tu k}
k1:=(k1+4 -d1 -1) mod 4 +1;
lui:=b1[k1];
end;
Function tich:longint;
var i:integer;
tg:longint;
begin
var i:integer;
tg:longint;
begin
tg:=1;
for i:=1 to 9 do
a[i]:=f[i,((a[i]-1) mod ff[i]) +1];
for i:=1 to 9 do
if a[i]<>0 then
tg:=tg*a[i];
tich:=tg mod 10;
end;
Procedure xuly;
var d,k:longint;
begin
read(n);
if n<=1 then
begin
writeln(1);
exit;
end;
init;
d:=0;
fillchar(a,sizeof(a),0);
while n<>0 do
begin
tinhtong(n);
n:=n div 5;
d:=d+n;
end;
k:=tich;
writeln(lui(k,d mod 4));
end;
begin
xuly;
readln;
end.
@boysitinh_vl:nếu bạn ko khinh tui vì hiểu biết thấp kém thì cho tui nói 1 tí.Có thể tài liệu của bạn nhiều thật,bạn cũng đã có 1 trình độ nhất định nào đó nhưng bạn có thể nể trọng người khác 1 chút xíu được ko.Ngay cả tên nick của bạn cũng đã thể hiện rồi,''vl'' là viết tắt của từ gì,có lẽ chúng tôi đều hiểu,chỉ là ngại ko nói ra.Nếu bạn có thể nằm trong top ten của IOI thì tui xin ngả mũ kính phục,còn lập 1 topic gây shock như bạn thì xin lỗi bạn,chúng tôi thà có 1 người có đức còn hơn có tài.
@mr_invincible:bạn có thể nói cho mình tư tưởng bài đó của bạn được ko.Dạo này mình cũng đang nghĩ nhiều về bài đó.
Bookmarks