分数: 300 点
问题陈述
正整数 n 被称为 好整数 当满足以下条件时:
- 恰好存在一对整数 (x,y) 满足 0 \lt x \lt y 和 x^2+y^2=n.
例如,当 n=2026,可以验证 (x,y)=(1,45) 是唯一满足以下条件的整数对 0 \lt x \lt y 和 x^2+y^2=n。因此, 2026 是一个很好的整数。
给你一个正整数 N。枚举所有不超过的好整数 N.
约束
- 1 \leq N \leq 10^7
- N 是一个整数。
输入
输入由标准输入按以下格式给出:
N
输出
让有 k 好的整数不超过 N,让 (a_1, a_2, \dots, a_k) 是这些整数的升序序列。按以下格式输出答案。 (如果 k=0,将第二行输出为空行。)
k a_1 a_2 \dots a_k
示例输入 1
10
示例输出 1
2 5 10
(x,y)=(1,2) 是唯一满足以下条件的整数对 0 \lt x \lt y 和 x^2+y^2=5,所以 5 是一个很好的整数。
(x,y)=(1,3) 是唯一满足以下条件的整数对 0 \lt x \lt y 和 x^2+y^2=10,所以 10 是一个很好的整数。
这是仅有的两个不超过的好整数 N.
示例输入 2
1
示例输出 2
0
示例输入 3
50
示例输出 3
14 5 10 13 17 20 25 26 29 34 37 40 41 45 50