#6568. 「Project Euler 9」特殊勾股数

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:Special Judge
上传者: moonoshawott

题目描述

一组勾股数由三个自然数组成, a < b < c ,且

a^2 + b^2 = c^2

例如, 3^2 + 4^2 = 9 + 16 = 25 = 5^2

给出 N ,请输出所有满足 a + b + c = N 的勾股数。

输入格式

只有一行,一个整数 N

输出格式

多行,每行三个整数, a, b, c ,表示答案。

样例

样例输入 1

12

样例输出 1

3 4 5

样例输入 2

120

样例输出 2

30 40 50
20 48 52
24 45 51

数据范围与提示

对于 20\% 的数据, N \leq 5000

对于 40\% 的数据, N \leq 1000000

对于 100\% 的数据, N \leq 10^{12}