Threeprimes (DHBB 2021 T.Thử)

Xem PDF




Thời gian:
Python 3 4.0s
Bộ nhớ:
Python 3 640M

Tác giả:
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\)\(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 phản hồi

    • 3
      dukksoocee3305412 10:20 p.m. 18 Tháng 4, 2021

      khó quá đại ca làm được chưa z


      • 2
        N7hoatt 11:54 a.m. 18 Tháng 4, 2021

        mới học thầy lâm xong thầy giải cho :))

        3 phản hồi