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

Đề tài: Findnum c++ spoj

  1. #1
    Ngày gia nhập
    09 2018
    Bài viết
    1

    Question Findnum c++ spoj

    FINDNUM - Tìm số
    Giới hạn
    Thời gian: 0.2s
    Bộ nhớ: 1536MB
    Mã nguồn: 50000 bytes
    Cho trước một số n. Hãy tìm số nguyên dương nhỏ nhất có đúng n ước.

    Dữ liệu vào
    - Một số nguyên n duy nhất (1 ≤ n ≤ 1000).

    Dữ liệu ra
    - Số nguyên dương nhỏ nhất (không vượt quá 10 18 ) có đúng n ước.
    (Biết rằng kết quả của các test luôn nằm trong giới hạn của đề)

    Ví dụ
    Input:
    4

    Output:
    6
    (Giới hạn: 50% số test có n ≤ 250)

    Cái này quy hoạch động thì full rồi, nhưng mình muốn làm đệ quy! Nhưng thử mãi thì mới có 30đ mong các pro tìm hiểu.
    My code::

    Code:
    #include <iostream>
    #include <math.h>
    using namespace std;
    
    long long res=100000000000000000,n,i,x,np=0;
    long long P[100000];
    
    void DQ(long long n, long long x, long long i)
    {
        if (1==n) {res=min(res,x); return;}
        for (int k=2;k<=n;k++)
        {
            if (n%k==0) 
            {
                long long y=pow(P[i],k-1);
                x*=y;
                DQ(n/k,x,i+1);
                x/=y;
            }
        }
    }
    int main()
    {
        cin>>n;
        for (int i=2;i<=100000;i++)
        {
            bool kt=true;
            for (int j=2;j*j<=i;j++)
               if (i%j==0)
               {
                  kt=false; break;
               }
            if (kt)
            {
              np++; P[np]=i;
            }
        }
        DQ(n,1,1);
        cout<<res;
    }

  2. #2
    Ngày gia nhập
    08 2017
    Bài viết
    2,211

    Trích dẫn Nguyên bản được gửi bởi quangduyluu123 Xem bài viết
    FINDNUM - Tìm số
    Giới hạn
    Thời gian: 0.2s
    Bộ nhớ: 1536MB
    Mã nguồn: 50000 bytes
    Cho trước một số n. Hãy tìm số nguyên dương nhỏ nhất có đúng n ước.

    Dữ liệu vào
    - Một số nguyên n duy nhất (1 ≤ n ≤ 1000).

    Dữ liệu ra
    - Số nguyên dương nhỏ nhất (không vượt quá 10 18 ) có đúng n ước.
    (Biết rằng kết quả của các test luôn nằm trong giới hạn của đề)

    Ví dụ
    Input:
    4

    Output:
    6
    (Giới hạn: 50% số test có n ≤ 250)

    Cái này quy hoạch động thì full rồi, nhưng mình muốn làm đệ quy! Nhưng thử mãi thì mới có 30đ mong các pro tìm hiểu.
    My code::
    đang cần tốc độ, mà chọn phương án đệ quy thì cầm chắc đội sổ.

    C++ Code:
    1. #include <iostream>
    2. #include <math.h>
    3. using namespace std;
    4.  
    5. long long res=100000000000000000,n,i,x,np=0;
    6. long long P[100000];
    7.  
    8. void DQ(long long n, long long x, long long i)
    9. {
    10.     if (1==n) {res=min(res,x); return;}
    11.     for (int k=2;k<=n;k++)
    12.     {
    13.         if (n%k==0)
    14.         {
    15.             long long y=pow(P[i],k-1);
    16.             x*=y;
    17.             DQ(n/k,x,i+1);
    18.             x/=y;
    19.         }
    20.     }
    21. }
    22. int main()
    23. {
    24.     cin>>n;
    25.     for (int i=2;i<=100000;i++)
    26.     {
    27.         bool kt=true;
    28.         for (int j=2;j*j<=i;j++)
    29.            if (i%j==0)
    30.            {
    31.               kt=false; break;
    32.            }
    33.         if (kt)
    34.         {
    35.           np++; P[np]=i;
    36.         }
    37.     }
    38.     DQ(n,1,1);
    39.     cout<<res;
    40. }

Tags của đề tài này

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