Threeprimes (DHBB 2021 T.Thử)

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

Từ thời cổ đại, mỗi chiến binh có một bộ ba loại vũ khí: một thanh kiếm laser, một lưỡi dao laser và một dao găm laser để trát bơ trên bánh mì (khi đói).

Những vũ khí này có ràng buộc về độ dài như sau:

  • Chiều dài dao găm - \(d_1\), chiều dài của lưỡi dao - \(d_2\), chiều dài của thanh kiếm - \(d_3\) đều là các số nguyên tố
  • \(d_1 \le d_2 \le d_3\)
  • \((d_1 + d_2)^2 - 1\) chia hết cho \(d_3\)
  • \((d_1 + d_3)^2 - 1\) chia hết cho \(d_2\)
  • \((d_2 + d_3)^2 - 1\) chia hết cho \(d_1\)

Công ty bán bất kỳ bộ vũ khí theo số thứ tự từ điển. Cụ thể, sắp xếp tất cả các bộ theo \(d_1\) không giảm, nếu \(d_1\) như nhau thì xét \(d_2\) không giảm, và nếu \(d_1\) và \(d_2\) bằng nhau thì xét \(d_3\) tăng và đánh số chúng theo thứ tự từ \(1\) đến vô cùng.

Cho \(k\), hãy mua tập vũ khí thứ \(k\) theo thứ tự này.

Input

  • Một dòng duy nhất ghi số nguyên \(k (1 ≤ k ≤ 60000)\).

Output

  • In ra độ dài 3 loại vũ khí trong tập thứ \(k\).

Example

Test 1

Input 
1
Output 
2 2 3

Bình luận


  • 20
    SPyofgame    8:47 a.m. 19 Tháng 4, 2021

    Hint:

    • Với \(d1\) là số nguyên tố bất kì, và \(f(a, b, c)\) là bộ ba số nguyên tố

    Ta chứng minh \((d1, d2, d3) = (d1, d1, 2 * d1 - 1)\) hoặc/và \((d1, d2, d3) = (d1, d1, 2 * d1 + 1)\)

    • Lưu ý là khi sàng nguyên tố, với \(k = 60.000\) thì sàng tới \(9737954 \approx 10^7\)

    • 2
      9Duy    11:06 p.m. 21 Tháng 4, 2021

      anh cho em hỏi là k=60000 thì sàng tới 9737954≈107 tính ntn mà ra vậy à em cảm ơn anh ạ


      • 3
        SPyofgame    12:29 p.m. 22 Tháng 4, 2021

        Vì ta có \(max(d_1, d_2, d_3)\) tại iteration \(60000\) là \(9737953\)


      • 1
        HDfake1    6:02 p.m. 19 Tháng 4, 2021

        Anh cho em hỏi là chứng minh như thế nào với ạ, em cảm ơn a


        • 1
          SPyofgame    10:17 p.m. 19 Tháng 4, 2021

          Mình chứng minh ở đây bạn


          • 4
            nothere    7:50 p.m. 19 Tháng 4, 2021 ← đã chỉnh sửa

            Ta có: (d1+d2)^2-1 = (d1+d2+1) x (d1+d2-1) chia hết cho d3

            Nếu d1+d2-1 là số nguyên tố thì giả sử nó là d3 (dễ chứng minh d1+d2-1 >= d2 >= d1), lại có:

            (d1+d3)^2-1 = (d1+d1+d2-1)^2-1 = (2 x d1+d2-2)(2 x d1+d2) chia hết cho d2

            TH1. 2 x d1 + d2 - 2 chia hết cho d2 => 2 x d1-2 chia hết cho d2 => d1-1 chia hết cho d2 (không thỏa mãn vì d1<=d2)

            TH2. 2 x d1 + d2 chia hết cho d2 => 2 x d1 chia hết cho d2 => d1 chia hết cho d2, mà d1<=d2 => d1=d2.

            TH còn lại CM tương tự nha em, anh xin lỗi anh hơi noob viết tutorial :v

          2 bình luận nữa