VNOI - Olympic tin học Việt Nam - Trả lời: Bài toán tính số chữ số 0 tận cùng của N! (phần vòng lặp)

	Mất mật khẩu? \| Đăng ký		Web VNOI Nộp mẫu đơn tìm kiếm

Điểm tin VOJ

Số thành viên:	6040
Số bài tập:	1001
Số bài nộp:	722923
Bài nộp hôm nay:	0

Top 10 thành viên xuất sắc

Hạng	Thành viên	Điểm
1	mr_invincible	587.9
2	white_cobra	418.6
3	hieult	403.4
4	phaleq	384.0
5	vodanh9x	368.2
6	con_nha_ngheo	352.0
7	flash_mt	350.2
8	darksabers	349.8
9	yenthanh132	345.3
10	rockman9x_94	343.1

Xem đầy đủ

Danh tiếng các thành viên

Hạng	Thành viên	Điểm
1	mr_invincible	+213
2	conankudo	+149
3	khuc_tuan	+137
4	tuananhnb93	+129
5	khanhptnk	+108
6	hphong	+103
7	flash_mt	+99
8	paulmcvn	+71
9	technolt	+70
10	hoangle	+63

Xem đầy đủ

Topcoder Vietnam

Hạng	Thành viên	Điểm

Diễn đàn

	Forum	DIỄN ĐÀN Hiển thị dạng cây

Forum

Học tập

Thuật toán

Bài toán tính số chữ số 0 tận cùng của N! (phần vòng lặp) (1 đang xem) ,(1) Khách

Được ưa thích: 1

Trang:
<< < 1 2 > >>

CHỦ ĐỀ - Bài toán tính số chữ số 0 tận cùng của N! (phần vòng lặp)

Công cụ diễn đàn

#64031

pe_nhok_su (Thành viên)
pe_nhok_su^-

Biết code binary-indexed tree

Bài viết: 22

Bài toán tính số chữ số 0 tận cùng của N! (phần vòng lặp) 8 năm, 6 tháng trước

(+0)

Cho N bất kì (ví dụ N=20). Hãy tính số chữ số 0 tận cùng của số N!

Giai thừa là phép toán rất lớn mà em lại chưa có thuật toán nào tối ưu cả, chỉ cần cho N>25 là bài của em sẽ sai ngay vì vượt quá giới hạn của kiểu dữ liệu. Các anh chị có thể cho em tham khảo một số thuật toán tối ưu để giải quyết được bài này không ạ?

Đã lưu IP

Đã khóa chức năng gửi bài.

#64043

mikelhpdatke (Thành viên)
mikelhpdatke

Đã biết code đệ quy

Bài viết: 7

Trả lời: Bài toán tính số chữ số 0 tận cùng của N! (phần vòng lặp) 8 năm, 6 tháng trước (+0)

Viết các chữ số tận cùng của 5!,25!,50!,... la` bạn sẽ tìm ra quy luật

Code:

Var n:Longint;
 
Procedure Init;
Var  m,KQ,t,dem:Longint;
Begin
 Readln(n);
 m:=n;
If m>=25 then
 Begin
   If m mod 25=0 then
     Begin
       t:=m div 25;
       KQ:=6*t;
       writeln(KQ);
      End
    Else
      Begin
        dem:=0;
        Repeat
          dec(m);
          if m mod 5=0 then inc(dem);
        Until m mod 25=0;
        t:=m div 25;
        KQ:=6*t+dem;
        writeln(KQ);
     End;
   End
Else
   Begin
      If m mod 5 =0 then
        Begin
          KQ:=m div 5;
          writeln(KQ);
        End
      Else
        Begin
          Repeat
           dec(m);
          Until m mod 5=0;
          KQ:=m div 5;
          writeln(KQ);
        End;
     End;
End;
BEGIN
iNit;
readln
end.

Đã lưu IP

Đã khóa chức năng gửi bài.

#64061

royalsilver16 (Thành viên)
royalsilver16⁺¹

Super fast coder

Bài viết: 78

Trả lời: Bài toán tính số chữ số 0 tận cùng của N! (phần vòng lặp) 8 năm, 6 tháng trước

(+0)

pe_nhok_su viết:

QUOTE:
Cho N bất kì (ví dụ N=20). Hãy tính số chữ số 0 tận cùng của số N!

Giai thừa là phép toán rất lớn mà em lại chưa có thuật toán nào tối ưu cả, chỉ cần cho N>25 là bài của em sẽ sai ngay vì vượt quá giới hạn của kiểu dữ liệu. Các anh chị có thể cho em tham khảo một số thuật toán tối ưu để giải quyết được bài này không ạ?

Công thức Lagrange

Số mũ của p trong n! là
[n / (p ^ 1)] + [n / (p ^ 2)] + [n / (p ^ 3)] + .. + [n / (p ^ oo)]

Đã lưu IP

I do what I like
I like what I do

Đã khóa chức năng gửi bài.

#64062

joker1569 (Thành viên)

Đã biết code đệ quy

Bài viết: 18

Trả lời: Bài toán tính số chữ số 0 tận cùng của N! (phần vòng lặp) 8 năm, 6 tháng trước

(+0)

Ban co the de dang nhan ra so chu so 0 tan cung cua n! phu thuoc vao so thua so 2 va 5 sau khi phan tich tat ca cac so tu 1 toi n ra thua so ng to, vay van de cua ban chi la tim mot cach nao do de xac dinh so thua so 2 va 5 thoi (qhd, for trau, tinh tay...) ban muon lam kieu j cung dc. Neu ban co cach tim tot thi voi n lon (vd n= 10^6) van co cach xac dinh dc so cs 0 tan cung cua n!

Than ai!
p/s: vietkey hong?

Đã lưu IP

Đã khóa chức năng gửi bài.

#64064

pe_nhok_su (Thành viên)
pe_nhok_su^-

Biết code binary-indexed tree

Bài viết: 22

Trả lời: Bài toán tính số chữ số 0 tận cùng của N! (phần vòng lặp) 8 năm, 6 tháng trước

(+0)

joker1569 viết:

QUOTE:
Ban co the de dang nhan ra so chu so 0 tan cung cua n! phu thuoc vao so thua so 2 va 5 sau khi phan tich tat ca cac so tu 1 toi n ra thua so ng to, vay van de cua ban chi la tim mot cach nao do de xac dinh so thua so 2 va 5 thoi (qhd, for trau, tinh tay...) ban muon lam kieu j cung dc. Neu ban co cach tim tot thi voi n lon (vd n= 10^6) van co cach xac dinh dc so cs 0 tan cung cua n! :D
Than ai!
p/s: vietkey hong? =((

Em đã nhận ra điều đó rồi nhưng thuật toán lại dở nên chỉ chạy được số nhỏ thôi. Em phải làm sao đây?

Đã lưu IP

Đã khóa chức năng gửi bài.

#64065

studytolive (Thành viên)
studytolive⁺⁵

Super fast coder

Bài viết: 59

Trả lời: Bài toán tính số chữ số 0 tận cùng của N! (phần vòng lặp) 8 năm, 6 tháng trước

(+1)

pe_nhok_su viết:

QUOTE:
joker1569 viết:

QUOTE:
Ban co the de dang nhan ra so chu so 0 tan cung cua n! phu thuoc vao so thua so 2 va 5 sau khi phan tich tat ca cac so tu 1 toi n ra thua so ng to, vay van de cua ban chi la tim mot cach nao do de xac dinh so thua so 2 va 5 thoi (qhd, for trau, tinh tay...) ban muon lam kieu j cung dc. Neu ban co cach tim tot thi voi n lon (vd n= 10^6) van co cach xac dinh dc so cs 0 tan cung cua n! :D
Than ai!
p/s: vietkey hong? =((

Em đã nhận ra điều đó rồi nhưng thuật toán lại dở nên chỉ chạy được số nhỏ thôi. Em phải làm sao đây?

Ơ kìa . thuật toán đã hiểu và công thức cũng có ở dưới kia thì bạn còn băn khoăn gì nữa

Thanks for reading

Đã lưu IP

So Try

Đã khóa chức năng gửi bài.

#64088

joker1569 (Thành viên)

Đã biết code đệ quy

Bài viết: 18

Trả lời: Bài toán tính số chữ số 0 tận cùng của N! (phần vòng lặp) 8 năm, 6 tháng trước	(+0)
Ban da nhan ra roi` thi don gian? nhat ban cung phai? viet duoc vong lap de xac dinh tu 1 toi n co bao nhieu thua so 2 va 5 chu. Ke ca? may cui` (nhu may' cua? minh) van co the dam bao? hai vong lap chay den 1000000 (chu dung noi la 20) ko qua thoi gian. Chi la ban qua cau ne viec tinh trau thoi. Ban viet code chay thu di, co gi sai dem len day cho moi nguoi mo? xe giup cho Than ai!

Đã lưu IP

Đã khóa chức năng gửi bài.

#64350

baolaptrinh (Thành viên)
baolaptrinh⁺³

Đã code là AC

Bài viết: 101

Trả lời: Bài toán tính số chữ số 0 tận cùng của N! (phần vòng lặp) 8 năm, 5 tháng trước	(+0)
Bạn 'joker1569' gõ tiếng Việt có dấu nhé!!!Viết thế mình đọc hay nhầm lắm!!!

Đã lưu IP

Đã khóa chức năng gửi bài.

#64889

thanhtoanth (Thành viên)

Đang tập code

Bài viết: 2

Trả lời: Bài toán tính số chữ số 0 tận cùng của N! (phần vòng lặp) 8 năm, 5 tháng trước

(+0)

pe_nhok_su viết:

QUOTE:
joker1569 viết:

QUOTE:
Ban co the de dang nhan ra so chu so 0 tan cung cua n! phu thuoc vao so thua so 2 va 5 sau khi phan tich tat ca cac so tu 1 toi n ra thua so ng to, vay van de cua ban chi la tim mot cach nao do de xac dinh so thua so 2 va 5 thoi (qhd, for trau, tinh tay...) ban muon lam kieu j cung dc. Neu ban co cach tim tot thi voi n lon (vd n= 10^6) van co cach xac dinh dc so cs 0 tan cung cua n! :D
Than ai!
p/s: vietkey hong? =((

Em đã nhận ra điều đó rồi nhưng thuật toán lại dở nên chỉ chạy được số nhỏ thôi. Em phải làm sao đây?

zay niu yêu cầu mình tinh tới giai thừa của 20000 thi sẽ ntn.
bài này nên sử dụng một mảng một chiều mà mỗi phần tử là một chữ số của giai thừa cần tìm rồi duyệt lại để đếm số chữ số 0

Đã lưu IP

Đã khóa chức năng gửi bài.

#64890

thanhtoanth (Thành viên)

Đang tập code

Bài viết: 2

Trả lời: Bài toán tính số chữ số 0 tận cùng của N! (phần vòng lặp) 8 năm, 5 tháng trước	(+0)
nếu 20000! thì mình phải làm sao

Đã lưu IP

Đã khóa chức năng gửi bài.

Trang:
<< < 1 2 > >>

Mục lục diễn đàn

Học tập

Thuật toán