/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
正整数 n が次の条件を満たす時、n を 良い整数 と呼びます。
- 0 \lt x \lt y かつ x^2+y^2=n を満たす整数の組 (x,y) がただ 1 つ存在する。
例えば n=2026 とすると、0 \lt x \lt y かつ x^2+y^2=n を満たす整数の組は (x,y)=(1,45) しか存在しないことが確認できます。よって 2026 は良い整数です。
正整数 N が与えられます。N 以下の良い整数を全て列挙してください。
制約
- 1 \leq N \leq 10^7
- N は整数
入力
入力は以下の形式で標準入力から与えられる。
N
出力
N 以下の良い整数が k 個あり、それらを昇順に並べた列が (a_1, a_2, \dots, a_k) であるとする。この時、以下の形式で答えを出力せよ。(k=0 である場合は 2 行目は空行として出力せよ。)
k a_1 a_2 \dots a_k
入力例 1
10
出力例 1
2 5 10
0 \lt x \lt y かつ x^2+y^2=5 を満たす整数の組は (x,y)=(1,2) しか存在しないので 5 は良い整数です。
0 \lt x \lt y かつ x^2+y^2=10 を満たす整数の組は (x,y)=(1,3) しか存在しないので 10 は良い整数です。
N 以下の良い整数はこの 2 個のみです。
入力例 2
1
出力例 2
0
入力例 3
50
出力例 3
14 5 10 13 17 20 25 26 29 34 37 40 41 45 50
Score : 300 points
Problem Statement
A positive integer n is called a good integer when it satisfies the following condition:
- There exists exactly one pair of integers (x,y) that satisfies 0 \lt x \lt y and x^2+y^2=n.
For example, when n=2026, it can be verified that (x,y)=(1,45) is the only pair of integers that satisfies 0 \lt x \lt y and x^2+y^2=n. Thus, 2026 is a good integer.
You are given a positive integer N. Enumerate all good integers not exceeding N.
Constraints
- 1 \leq N \leq 10^7
- N is an integer.
Input
The input is given from Standard Input in the following format:
N
Output
Let there be k good integers not exceeding N, and let (a_1, a_2, \dots, a_k) be the sequence of these integers in ascending order. Output the answer in the following format. (If k=0, output the second line as an empty line.)
k a_1 a_2 \dots a_k
Sample Input 1
10
Sample Output 1
2 5 10
(x,y)=(1,2) is the only pair of integers that satisfies 0 \lt x \lt y and x^2+y^2=5, so 5 is a good integer.
(x,y)=(1,3) is the only pair of integers that satisfies 0 \lt x \lt y and x^2+y^2=10, so 10 is a good integer.
These are the only two good integers not exceeding N.
Sample Input 2
1
Sample Output 2
0
Sample Input 3
50
Sample Output 3
14 5 10 13 17 20 25 26 29 34 37 40 41 45 50