Từ 1 tới 9 trên tổng số 9 kết quả

Đề tài: Tìm số nguyên dương nhỏ nhất có đúng n ước số

  1. #1
    Ngày gia nhập
    10 2011
    Bài viết
    17

    Mặc định Tìm số nguyên dương nhỏ nhất có đúng n ước số

    Như tiêu đề,em muốn tìm số nguyên dương nhỏ nhất có đúng n ước số.Em nghĩ là có thể giải bằng phương pháp quy hoạch động. Nhg vẫn còn mơ hồ lắm,chưa ra gì cả. Các bác giúp em với.

  2. #2
    Ngày gia nhập
    05 2011
    Bài viết
    39

    Trích dẫn Nguyên bản được gửi bởi minhtuan.a0 Xem bài viết
    Như tiêu đề,em muốn tìm số nguyên dương nhỏ nhất có đúng n ước số.Em nghĩ là có thể giải bằng phương pháp quy hoạch động. Nhg vẫn còn mơ hồ lắm,chưa ra gì cả. Các bác giúp em với.
    Bài này có lẽ dùng thuật toán vét cạn cũng được .

  3. #3
    Ngày gia nhập
    10 2011
    Bài viết
    17

    Vét cạn không ổn. Giới hạn n <= 1000. Kqua in ra ko vượt quá 10^8.
    n<=1000 rõ ràng là dùng DP vs độ phức tạp là O(n^2). Nghĩ mãi chả ra =="

  4. #4
    Ngày gia nhập
    11 2010
    Bài viết
    589

    Cần gì phải vét cạn cực khổ vậy chứ, dùng một vài kiến thức số học là có cách nhanh hơn:
    - Một số m có phân tích nguyên tố:
    Công thức toán học Latex
    Sẽ có số nghiệm là:
    Công thức toán học Latex
    - Việc bây giờ là với n là số ước cho trước, hãy tìm các bộ c0, c1, ... thoả mãn, từ đó tìm ra các số m tương ứng và cả số nhỏ nhất trong đó. Chú ý là dãy c0, c1 ... này là dãy không tăng. Xem thêm: en.m.wikipedia.org/wiki/Highly_composite_number
    Đã được chỉnh sửa lần cuối bởi boss14420 : 30-03-2012 lúc 10:32 PM.

  5. #5
    Ngày gia nhập
    05 2011
    Bài viết
    39

    Trích dẫn Nguyên bản được gửi bởi boss14420 Xem bài viết
    Cần gì phải vét cạn cực khổ vậy chứ, dùng một vài kiến thức số học là có cách nhanh hơn:
    - Một số m có phân tích nguyên tố:
    Công thức toán học Latex
    Sẽ có số nghiệm là:
    Công thức toán học Latex
    - Việc bây giờ là với n là số ước cho trước, hãy tìm các bộ c0, c1, ... thoả mãn, từ đó tìm ra các số m tương ứng và cả số nhỏ nhất trong đó. Chú ý là dãy c0, c1 ... này là dãy không tăng. Xem thêm: en.m.wikipedia.org/wiki/Highly_composite_number
    Hi , ban nãy em cũng phân tích số học , thu được 1 biểu thức rời rạc , nhưng không biết phân tích thành nhân tử tiếp .
    Nhưng cách này làm tiếp cũng phức tạp .

  6. #6
    Ngày gia nhập
    10 2011
    Bài viết
    17

    Mặc định Tìm số nguyên dương nhỏ nhất có đúng n ước số

    Cách của bác hình như ko ổn lắm :-?.
    Nếu làm như thế ta sẽ phải thực hiện nhiều phép tính mũ rồi nhân với nhau rồi :-?

  7. #7
    Ngày gia nhập
    11 2010
    Bài viết
    589

    Ta có thể xây dựng dãy c0, c1, ... bằng giải thuật quay lui, các số ci được lấy từ 1 cho đến min(n/((c0+1)*(c1+1)*...*(c(i-1) + 1))-1,c(i-1)), các lũy thừa được tính dần từ phép lặp kia.

    C++ Code:
    1.  
    2. typedef unsigned long long ull;
    3. typedef unsigned int uint;
    4. uint p = { 2, 3, 5, 7, 11, 13, 17, 19, 23 }; //Tạm thời chỉ cần 9 số nguyên tố vì n <= 1000;
    5. uint c[9];
    6. uint remain; // = n/((c0+1)*(c1+1)*...*(c(i-1) + 1))
    7. ull result; // kết qủa, số nhỏ nhất có n ước
    8.  
    9. void find(int i, ull m) {
    10.     m *= p[i];
    11.     uint min = min(c[i-1], remain-1);
    12.     for( uint j = 1; j <= min && m < result; ++j, m*=p[i]) {
    13.             if(!(remain % (j+1))) {
    14.                 c[i] = j;
    15.                 remain /= (j+1);
    16.                 if(1 == remain) {
    17.                          result = m; // cập nhật số nhỏ nhât
    18.                  } else find(i+1, m);
    19.                  // trả lại trạng thái
    20.                  remain *= (j+1);
    21.             }
    22.      }
    23. }
    Đã được chỉnh sửa lần cuối bởi boss14420 : 31-03-2012 lúc 12:22 AM.

  8. #8
    Ngày gia nhập
    09 2009
    Nơi ở
    Hoa sơn tuyệt đỉnh
    Bài viết
    407

    - n=1000 số lớn hơn 10^18 á, muốn QHĐ n^2 thì phải cài số lớn, mình đã code thử nhưng ko đủ bộ nhớ mảng n*n*(độ dài số lớn) (có thể mình gà)
    - Mình AC bằng quay lui kết hợp cận
    https://vn.spoj.pl/problems/FINDNUM/

    https://vn.spoj.pl/status/FINDNUM,hunterphu/

    my houses
    my school
    tỐnG lÊ cHâN mAnG kỶ nIệM bUồN cHo AnH...

  9. #9
    Ngày gia nhập
    11 2010
    Bài viết
    589

    Xem bài của bác hunterphu mới nhớ ra là mình đã làm bài này. Giải thuật hồi đó cũng khá tương tự nhưng "ngây thơ" hơn code trên kia, nhưng vẫn chỉ mất có 0.00s
    http://vn.spoj.pl/status/FINDNUM,boss14420/

Các đề tài tương tự

  1. Tối ưu Code nhập số nguyên dương rồi đảo ngược số nguyên dương vừa nhập trong C
    Gửi bởi tyrant trong diễn đàn Thảo luận, góp ý code C/C++ của bạn
    Trả lời: 12
    Bài viết cuối: 21-06-2018, 06:19 PM
  2. Bài tập C bài toán phân tích số nguyên dương, dùng phương pháp sinh, kết quả không đúng?
    Gửi bởi xuannam2620 trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 8
    Bài viết cuối: 11-03-2012, 11:24 PM
  3. Bài quản lý sinh viên viết bằng C#. Hàm nhập bị lỗi không thể nhập đúng được?
    Gửi bởi gaconnho trong diễn đàn Thắc mắc lập trình C#
    Trả lời: 7
    Bài viết cuối: 23-12-2010, 12:37 PM
  4. Làm sao kiểm tra tính đúng đắn vấn đề xử lý số nguyên lớn trên C/C++?
    Gửi bởi phuc_tran trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 7
    Bài viết cuối: 10-09-2010, 11:35 AM

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn