Số nguyên tố cân bằng (HSG'21)

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

Một số được gọi là số nguyên tố cân bằng nếu nó là số nguyên tố có \(2k + 1\) chữ số \((k \in \mathbb{N}^*)\), trong đó có \(2k\) chữ số giống nhau và có đúng \(1\) chữ số ở vị trí chính giữa (tức vị trí thứ \(k + 1\) từ trái sang phải) là khác với các chữ số còn lại.

Ví dụ: Số \(7778777\) là số cân bằng.

Yêu cầu:

Nhập từ bàn phím \(1\) số nguyên dương \(k\) \((k \le 7)\). Hãy tính và in ra màn hình số lượng các số nguyên tố cân bằng có \(2k + 1\) chữ số.

Example

Test 1

Input 
3
Output 
7
Note

Có \(7\) số nguyên dương có \(2 \times 3 + 1\) chữ số là số nguyên tố: \(1114111;1117111; 3331333; 3337333; 7772777; 7774777; 7778777\)

Bình luận


  • -1
    penistone    10:04 p.m. 14 Tháng 9, 2024

    bài này tưởng phải dùng miller-rabin ☠️


    • 6
      khai234991    6:00 p.m. 16 Tháng 1, 2024

      SPOILER ALERT
      ------------------------------

      BRUTE FORCE (AC):
      using namespace std;
      bool snt(int n)
      {
      if (n < 2) return 0;
      if (n < 4) return 1;
      if (n % 2 == 0 || n % 3 == 0)
      return 0;
      for (int i = 5 ; i <= sqrt(n) ; i+=6)
      if (n % i == 0 || n % (i+2) == 0) return 0;
      return 1;
      }
      int a[10];
      signed main()
      {
      int n; cin >> n;
      for (int i = 1 ; i <= 9 ; i++) a[i] = i;
      for (int i = 2 ; i <= n ; i++)
      for (int j = 1 ; j <= 9 ; j++)
      {
      a[j] = a[j]10+j;
      }
      //test
      int dem = 0;
      for (int i = 0 ; i <= 9 ; i++)
      for (int j = 1 ; j <= 9 ; j++)
      {
      long long ans = (a[j]      10+i)*pow(10,n)+a[j];
      if (snt(ans)) dem++;
      }
      cout << dem;
      }
      Dành cho những bạn nào bị bí ý tưởng có thể tham khảo. Mong mọi người đừng downvote!


      • -11
        havanxt    11:18 p.m. 19 Tháng 9, 2023

        Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.

        1 phản hồi

        • 21
          dang7rickroll    8:27 p.m. 8 Tháng 1, 2022 ← đã chỉnh sửa

          Spoiler Alert

          Thực ra bài này có thuật toán cực kỳ dễ (chỉ đơn giản là kiểm tra số nguyên tố), tuy nhiên thử thách lớn nhất ở đây chính là việc vét hết toàn bộ các số có thể, và bạn (cần) phải có kỹ năng code ở mức trung bình \(\rightarrow\) cao.

          Hướng dẫn

          • Ta vét hét toàn bộ trường hợp có thể (do giới hạn của \(k\) chỉ \(\le 7\)).
          • Với mỗi trường hợp vét được, ta kiểm tra tính nguyên tố của số đó. Nếu hợp lệ, tăng biến đếm lên \(1\).

          Tiếp cận

          • Ta cho hai vòng \(for\), \(1\) vòng \(a\) chạy từ \(1\) đến \(9\), \(1\) vòng \(b\) chạy từ \(0\) đến \(7\), và khi xét thì phải kiểm tra thêm điều kiện là \(a\) phải khác \(b\).
          • Giải thích: \(a\) chính là phần trước và phần sau của chữ số chính giữa (chữ số chính giữa là chữ số thứ \(k + 1\)), \(b\) chính là chữ số thứ \(k + 1\), và theo đề là nó phải khác nhau. Ví dụ \(7778777\) thì phần \(a\) là \(7\), phần \(b\) là \(8\).
          • Khi \(a,b\) thỏa mãn điều kiện \(a \neq b\) thì ta sẽ đưa \(k\) số \(a\) đầu tiên vào một biến khác (ở đây là biến \(n\)).
          • Sau đó đưa số \(b\) vào giữa.
          • Tiếp đó, đưa \(k\) số \(a\) vào phía sau số \(n\).
          • Cuối cùng, việc chúng ta là kiểm tra tính nguyên tố của \(n\), nếu thỏa mãn thì tăng biến đếm lên, nếu không thỏa mãn thì tiếp tục vòng lặp.

          Độ phức tạp

          Vì ta chạy hai vòng \(for\), mỗi vòng chạy đến \(9\), cộng thêm hàm kiểm tra số nguyên tố của \(n\) có \(2k + 1\) chữ số, vậy độ phức tạp tổng quát của bài này là \(\boxed{\mathcal{O}(9^2 + \sqrt{10^{2n + 1}})}\).

          • Trường hợp xấu nhất (\(k = 7\)) thì độ phức tạp của nó là \(\mathcal{O}(81 * \sqrt{10^{15}})\), vì vậy với trường hợp này ta nên if-test để tránh bị TLE test cuối.

          Code tham khảo

          Mình biết là mình giải thích hơi khó hiểu nên bạn có thể tham khảo code của mình

          \(\color{green}{\text{Preference Accepted Code}}\): Cài đặt, số nguyên tố

          C++
           for (int a = 1; a <= 9; a++)
  {
    for (int b = 0; b <= 9; b++)
    {
        if (a != b)
        {
            int n = 0;
            for (int i = 0; i < k; i++)
            {
                n = n * 10 + a;
            }
            n = n * 10 + b;
            for (int i = 0; i < k; i++)
            {
                n = n * 10 + a;
            }
            if (isPrime(n) == true) res++;
        }
    }
  }

          P/s: Nếu có gì sai sót, bạn có thể comment, xin đừng downvote, mình cảm ơn 😢

          1 phản hồi

          • -2
            stack_queue_4977    7:59 a.m. 3 Tháng 1, 2022

            Mình đã chỉnh lại đề.


            • 3
              lequangdat0405    4:36 p.m. 2 Tháng 1, 2022

              Ai cho mình xin ý tưởng bài này với :V


              • 8
                khanh3327    6:03 p.m. 10 Tháng 9, 2021

                số 171 chia hết cho 3 sao đề bảo là số nguyên tố cân bằng nhỉ


                • 1
                  VoBaThongL921    11:26 a.m. 31 Tháng 8, 2021 ← đã chỉnh sửa

                  Mình chưa làm bài này, nhưng mình nghĩ số số nguyên tố cân bằng cũng ít thôi đúng ko nhỉ ?


                  • -22
                    Toilaaibanbietko7A4    5:25 p.m. 5 Tháng 7, 2021

                    Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.


                    • -10
                      dkm    4:51 p.m. 5 Tháng 7, 2021

                      Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.

                        • 3 bình luận nữa