Duyên Hải 2020 - Lớp 10 - Bài 2 - Số chính phương

Xem dạng PDF
Gửi bài giải
Điểm: 0,40 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Bình là một cậu bé rất đam mê toán học, đặt biệt là phần số học. Giải các bài toán về số nguyên tố, số chính phương, chia hết, ... là sở trường của Bình. Nhân dịp Kỳ thi Duyên hải năm nay được tổ chức lần đầu tiên theo hình thức thi online, Bình gửi đến các bạn một bài toán liên quan đến số chính phương.

Với số tự nhiên ~n~ cho trước, Bình yêu cầu bạn đếm số bộ ba số nguyên ~(a~, ~b~, ~c)~ với ~1 \le a < b < c \leq n~ sao cho tất cả các tích ~a \times b~, ~a \times c~ và ~b \times c~ đều là các số chính phương.

Input

Dữ liệu vào gồm duy nhất một số nguyên dương ~n~ ~(n \le 5 \cdot 10^6)~.

Output

Ghi ra số lượng bộ ~3~ số ~a~, ~b~, ~c~ tìm được.

Giới hạn

  1. ~(24~ điểm~)~ ~1 \leq n \leq 100~
  2. ~(20~ điểm~)~ ~100 < n \leq 5000~
  3. ~(28~ điểm~)~ ~5000 < n \leq 10^5~
  4. ~(28~ điểm~)~ ~10^{5} < n \leq 5.10^6~

Sample Input

20

Sample Output

5

Note

Với ~n = 20~ có tất cả ~5~ bộ là: ~(1~, ~4~, ~9)~; ~(1~, ~4~, ~16)~; ~(1~, ~9~, ~16)~; ~(4~, ~9~, ~16)~ và ~(2~, ~8~, ~18)~.

Bình luận

Hãy đọc nội quy trước khi bình luận.


  • 1
    SPyofgame  đã bình luận lúc 25, Tháng 1, 2023, 16:41 ← sửa 3

    HNCSPFTRs Bạn muốn hỏi về đoạn nào


  • 2
    SPyofgame  đã bình luận lúc 29, Tháng 10, 2021, 16:16

    Bài này có thể giải trong ~O(\sqrt{n} \log n)~ tại đây

    Bài này cũng có thể giải với ~1 \leq a_1 < a_2 < \dots < a_k \leq n~ trong ~O(\sqrt{n} \log n)~ (với ~1 \leq k \leq n < mod~)


    • -18
      HN_CSP_FTRs  đã bình luận lúc 5, Tháng 1, 2022, 4:21

      Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.