Diễn đàn tin học Nguyễn Văn Linh
Bạn có muốn phản ứng với tin nhắn này? Vui lòng đăng ký diễn đàn trong một vài cú nhấp chuột hoặc đăng nhập để tiếp tục.

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

The second house for every one
 
Trang ChínhLatest imagesTìm kiếmĐăng kýĐăng Nhập

 

 Bội chung nhỏ nhất

Go down 
3 posters
Tác giảThông điệp
Hovanthong
Admin
Admin
Hovanthong


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

Bội chung nhỏ nhất Empty
Bài gửiTiêu đề: Bội chung nhỏ nhất   Bội chung nhỏ nhất I_icon_minitimeTue 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
littlelee


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

Bội chung nhỏ nhất Empty
Bài gửiTiêu đề: Re: Bội chung nhỏ nhất   Bội chung nhỏ nhất I_icon_minitimeWed 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
Về Đầu Trang Go down
Hovanthong
Admin
Admin
Hovanthong


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

Bội chung nhỏ nhất Empty
Bài gửiTiêu đề: Re: Bội chung nhỏ nhất   Bội chung nhỏ nhất I_icon_minitimeThu 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?
Về Đầu Trang Go down
http://thongtra.forum-viet.com
littlelee
Admin
Admin
littlelee


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

Bội chung nhỏ nhất Empty
Bài gửiTiêu đề: Re: Bội chung nhỏ nhất   Bội chung nhỏ nhất I_icon_minitimeFri 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?
Về Đầu Trang Go down
Hovanthong
Admin
Admin
Hovanthong


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

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

Vẫn chưa nghĩ ra.CHỉ có cách N/2 thôi!
Về Đầu Trang Go down
http://thongtra.forum-viet.com
hieu1801
Gà mờ
hieu1801


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

Bội chung nhỏ nhất Empty
Bài gửiTiêu đề: Re: Bội chung nhỏ nhất   Bội chung nhỏ nhất I_icon_minitimeFri 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ờ
hieu1801


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

Bội chung nhỏ nhất Empty
Bài gửiTiêu đề: Re: Bội chung nhỏ nhất   Bội chung nhỏ nhất I_icon_minitimeFri 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
littlelee


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

Bội chung nhỏ nhất Empty
Bài gửiTiêu đề: Re: Bội chung nhỏ nhất   Bội chung nhỏ nhất I_icon_minitimeMon 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ể.
Về Đầu Trang Go down
Sponsored content





Bội chung nhỏ nhất Empty
Bài gửiTiêu đề: Re: Bội chung nhỏ nhất   Bội chung nhỏ nhất I_icon_minitime

Về Đầu Trang Go down
 
Bội chung nhỏ nhất
Về Đầu Trang 
Trang 1 trong tổng số 1 trang
 Similar topics
-
» nhập vào 2 số và tìm số nhỏ nhất ?
» Xóa số để tạo thành số nhỏ nhất, lớn nhất.
» Số lượng hình chữ nhật
» Dãy con tăng dài nhất
» Chu vi của n hình chữ nhật

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