[MASKTECH 2026] Câu 1. Số tốt

Tác giả:

Dạng bài

Ngôn ngữ cho phép

Assembly, Awk, C, C#, C++, Clang, Cobol, D, ~~Groovy~~, Haskell, JS, Java, Kotlin, Lua, Node JS, OCaml, ObjectiveC, Output, PHP, Pascal, Perl, Prolog, Pypy, Pypy 3, Python, Ruby, Rust, Scala, Scratch, ~~Swift~~

Điểm: 1100 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Một buổi chiều mưa, tiếng mưa rơi đều trên mái tôn của nhà văn hóa huyện. Ban tổ chức CLB tin học MaskTech đã chuẩn bị một mini hackathon bất ngờ cho các thành viên:
“Ai giải được bài toán bí ẩn sớm nhất sẽ được nhận phần thưởng.”

Chị Hương — thành viên mới — tò mò bước lên sân khấu. Trên màn hình hiện một thử thách, nét mực đã phai:

Ở Quảng Trị có một con số bí ẩn. Người ta gọi một số nguyên dương \(A\) là số tốt khi tồn tại chính xác một cặp số nguyên dương \((x, y)\) thỏa điều kiện:
\(0 < x < y\) và \(x^2 + y^2 = A\).

Yêu cầu: Liệt kê tất cả các số tốt không vượt quá một số cho trước \(n\).

Input

Một dòng duy nhất chứa số nguyên dương \(n\) (\(n \le 10^7\)).

Output

Ghi danh sách (theo thứ tự tăng dần) tất cả các số \(A \le n\) là số tốt. Các số được ghi trên cùng một dòng, cách nhau bởi dấu cách.

Example

Test 1

Input

Output

5 10 13 17 20

Note

\(5 = 1^2 + 2^2\) (1 cặp duy nhất: \((1, 2)\))
\(10 = 1^2 + 3^2\) (1 cặp duy nhất: \((1, 3)\))
\(13 = 2^2 + 3^2\) (1 cặp duy nhất: \((2, 3)\))
\(17 = 1^2 + 4^2\) (1 cặp duy nhất: \((1, 4)\))
\(20 = 2^2 + 4^2\) (1 cặp duy nhất: \((2, 4)\))
Số tốt chỉ liệt kê một lần.

Scoring

Subtask \(1\) (\(30\%\) số điểm): \(n \le 3000\).
Subtask \(2\) (\(70\%\) số điểm): \(n \le 10^7\).

Bình luận

Tải bình luận...

Không có bình luận nào.