Số đẹp (THTC - Q.Ninh 2021)

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Tác giả:
Small
Dạng bài
Điểm: 200 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

.

Bài 3: Số đẹp

.

Bình luận


  • 10
    Toilaaibanbietko7A4    10:01 a.m. 31 Tháng 8, 2021 ← chỉnh sửa 3

    SOLUTION

    Bài này có khá nhiều cách giải(có thể AC,WA,TLE,RTE... vân vân các kiểu), thế nhưng trong hầu hết cách bài nộp AC (ko có if) thì đều có sự xuất hiện của bài FACTOR. Thế nên mình lấy cơ sở này để viết, dành cho những bạn nào đang 'stuck' cách giải.

    Đầu tiên, như nói ở trên, ta phân tích n ra thừa số nguyên tố , ta có n = \(p1^a\) . \(p2^b\) . \(p3^c\) . \(p4^d\) . ... . \(pk^z\) (p1 , p2 , p3 , p4 , ... , pk là các số nguyên tố đôi 1 khác nhau ; a, b, c, d,...>0)

    Quay lại định nghĩa số đẹp, ta nhận thấy 1 số n không phải số đẹp khi có 1 số chính phương là ước, điều này đồng nghĩa với việc trong phần phân tích của n ở trên có ít nhất 1 phần tử làm mũ lớn hơn 1 (tức các a,b,c,d... ở trên).

    ==> n là số đẹp khi là số ko có bất kì ước nào là số chính phương , hay nói cách khác, là số mà khi phân tích thừa số nguyên tố ra thì không có bất kì phần tử làm mũ nào (tức các a,b,c,d... ở trên) lớn hơn 1.

    Vậy thì cần làm như thế nào? Bạn chỉ cần lấy p1p2p3...pk là có kết quả.

    Vậy là chúng ta đã có cơ sở để giải bài này rồi 🙂

    Nhưng quan trọng là code. Nội trong ý tưởng này, có tới 2 hướng giải: lập mảng để giải , và giải trực tiếp.

    Lập mảng để giải là tạo ra 1 mảng, lưu các số nguyên tố là ước của n, sau đó duyệt để lấy tích các số nguyên tố đó làm đáp án. Còn giải trực tiếp là khi n không còn chia hết cho 1 số nguyên tố nào đó (trước đó phải có chia hết cho n), ta lấy kết quả nhân với chúng là ra kết quả. Cần chú ý kiểm tra trước khi in ra nhé.

    Bạn giải cách nào cx đc cả. Riêng mình cho bạn coi cả hai cách giải của mình, để bạn có thể thấy đc sự khác nhau và tự đánh giá nhé. Và, đương nhiên, NGHIÊM CẤM CHÉP CODE.

    Cách 1:

    C++
    vector<int> Snt;
int main()
{
    long long n,i=2,kt=0,ans=1;
    cin>>n;
    while (i<=sqrt(n))
    {
        while (n%i==0) 
        {
            n=n/i;
            kt++;
        }
        if (kt>0) Snt.push_back(i);
        i++;
        kt=0;
    }
    Snt.push_back(n);
    int m=Snt.size();
    for (int j=1;j<=m;j++) ans=ans*Snt[j-1];
    cout<<ans;
}

    Cách 2:

    C++
    int main()
{
    long long n,i=2,kt=0,ans=1;
    cin>>n;
    while (i<=sqrt(n))
    {
        while (n%i==0)
        {
            n=n/i;
            kt++;
        }
        if (kt>0) ans=ans*i;
        i++;
        kt=0;
    }
    ans=ans*n;
    cout<<ans;
}

    P/s: Có khúc mắc, bất mãn gì thì cứ comment bên dưới, chứ đừng downvote nhé :))


    • 0
      mcsmuscle    1:37 p.m. 5 Tháng 10, 2021 ← đã chỉnh sửa

      cách 2 khúc này hình như bị thừa thì phải

       if (kt==1 && i!=n) ans=ans*i;
    1 bình luận nữa