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

Xem PDF

Đ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


  • 0
    new4letuantu 8:14 a.m. 13 Tháng 11, 2021

    giúp em ac hai test 17 và test 20 với ạ ;-;


    • 9
      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é :))

      1 phản hồi