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

Xem PDF
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


  • 18
    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 😢


    • 2
      nguyendanghau2006    11:52 p.m. 9 Tháng 1, 2022

      túi quá nghe 😝😝😝😝


      • 4
        huyhau6a2    6:57 p.m. 10 Tháng 1, 2022

        chòi oi tui tốn công sieve tới tận 4.10^7 đây nè huhu

      11 bình luận nữa