← 返回题目列表

AtCoder · abc439_c

E. 二〇二六

中文机器翻译题面 查看原题

分数: 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