Diễn đàn tin học Nguyễn Văn Linh

The second house for every one
 
IndexTrợ giúpTìm kiếmThành viênĐăng kýĐăng Nhập

Share | 
 

 Bội chung nhỏ nhất

Xem chủ đề cũ hơn Xem chủ đề mới hơn Go down 
Tác giảThông điệp
Hovanthong
Admin
Admin


Tổng số bài gửi : 101
Join date : 25/07/2010
Age : 22
Đến từ : Hưng nguyên-Nghệ An

Bài gửiTiêu đề: Bội chung nhỏ nhất   Tue 27 Jul 2010, 13:31

Cho nguyên dương N (1<=n<=350). Hãy tìm cách phân tích N thành tổng của một số số nguyên dương sao cho bội số chung nhỏ nhất của chúng là lớn nhất có thể.
Input

Dòng đầu tiên là T : Số test.

T dòng sao mỗi dòng là một số nguyên dương N (1<=n <=350).
Output

Với mỗi test cần in ra một số là bội chung nhỏ nhất tìm được.


Example

Input:
1
10

Output:

30
Về Đầu Trang Go down
http://thongtra.forum-viet.com
littlelee
Admin
Admin


Tổng số bài gửi : 415
Join date : 20/12/2009
Age : 21
Đến từ : Nghĩa địa

Bài gửiTiêu đề: Re: Bội chung nhỏ nhất   Wed 28 Jul 2010, 11:21

khá thú vị. Càng nhiều cặp nguyên tố cùng nhau, bcnn của chúng càng lớn.

Lần lượt phần tích i số, các số đó nguyên tố cùng nhau càng nhiều càng tốt.

Thấy làm kiểu đó mò mẫm. laughing

_________________
Đời là cây đinh, mình là cây búa.
Về Đầu Trang Go down
Hovanthong
Admin
Admin


Tổng số bài gửi : 101
Join date : 25/07/2010
Age : 22
Đến từ : Hưng nguyên-Nghệ An

Bài gửiTiêu đề: Re: Bội chung nhỏ nhất   Thu 29 Jul 2010, 22:22

Bài này làm O(N/2) thì sẽ chạy lâu. Ai có thuật toán gì tốt hơn không?

_________________
P.T.H.T
Về Đầu Trang Go down
http://thongtra.forum-viet.com
littlelee
Admin
Admin


Tổng số bài gửi : 415
Join date : 20/12/2009
Age : 21
Đến từ : Nghĩa địa

Bài gửiTiêu đề: Re: Bội chung nhỏ nhất   Fri 30 Jul 2010, 10:42

Em có cách này coi bộ cũng tạm, đỡ hơn mò mẫm.

Áp dụng toán học vào để giải ^^. Lần lượt tìm tất cả các số nguyên tố từ 1-->350 lưu vào 1 mảng. Gọi các số có được khi phân tích N ra là a1,a2,..ah. Gọi k là số lượng các ước nguyên tố trong các phân tích dãy trên ra thừa số nguyên tố. QHD để xem có thể phân tích dc hay ko.

Ý tưởng thế thôi, chứ thực h9ieenj cũng khó. Anh Thông có cách nào khác hok?

_________________
Đời là cây đinh, mình là cây búa.
Về Đầu Trang Go down
Hovanthong
Admin
Admin


Tổng số bài gửi : 101
Join date : 25/07/2010
Age : 22
Đến từ : Hưng nguyên-Nghệ An

Bài gửiTiêu đề: Re: Bội chung nhỏ nhất   Fri 30 Jul 2010, 14:46

Vẫn chưa nghĩ ra.CHỉ có cách N/2 thôi!

_________________
P.T.H.T
Về Đầu Trang Go down
http://thongtra.forum-viet.com
hieu1801
Gà mờ


Tổng số bài gửi : 8
Join date : 21/07/2010

Bài gửiTiêu đề: Re: Bội chung nhỏ nhất   Fri 27 Aug 2010, 23:11

Em thấy có bài toán phân tích N ra thành tổng các số nguyên dương. Ta có thể áp dụng bài toán này bằng cách: Mỗi bước có một dãy số (có tổng bằng N) ta tìm BCNN của chúng rồi tìm Max luôn không??!
Về Đầu Trang Go down
hieu1801
Gà mờ


Tổng số bài gửi : 8
Join date : 21/07/2010

Bài gửiTiêu đề: Re: Bội chung nhỏ nhất   Fri 27 Aug 2010, 23:15

Em thấy có bài toán phân tích N ra thành tổng các số nguyên dương. Ta có thể áp dụng bài toán này bằng cách: Mỗi bước có một dãy số (có tổng bằng N) ta tìm BCNN của chúng rồi tìm Max luôn không??!
Về Đầu Trang Go down
littlelee
Admin
Admin


Tổng số bài gửi : 415
Join date : 20/12/2009
Age : 21
Đến từ : Nghĩa địa

Bài gửiTiêu đề: Re: Bội chung nhỏ nhất   Mon 30 Aug 2010, 14:00

Ko dc đâu. Em biết n=100 có bao nhiêu cách phân tích ko. Có trên 190 triệu cách phân tích đấy. Còn 350 thì có trên 5*10^18 cách phân tích. Thử là điều ko thể.

_________________
Đời là cây đinh, mình là cây búa.
Về Đầu Trang Go down
Sponsored content




Bài gửiTiêu đề: Re: Bội chung nhỏ nhất   Today at 21:32

Về Đầu Trang Go down
 
Bội chung nhỏ nhất
Xem chủ đề cũ hơn Xem chủ đề mới hơn Về Đầu Trang 
Trang 1 trong tổng số 1 trang
 Similar topics
-
» Chung mộng - Như Quỳnh
» [Top 5 ông chồng sao nào sẽ tuyệt đối chung tình ko lăng nhăng]
» Điểm mặt những "anh tài" tham gia vòng Chung kết toàn quốc cuộc thi Chinh Phụ Vũ Môn lần thứ II
» Trứng gà tác hại...
» TẮM RỬA CHO CHÚNG SINH ĐAU KHỔ

Permissions in this forum:Bạn không có quyền trả lời bài viết
Diễn đàn tin học Nguyễn Văn Linh :: Góc tin học :: Lớp chuyên tin-
Chuyển đến