#LQB0058. 多边形数

多边形数

提示信息:

三角形数:对于整数 n,如果可以将 n 个点排列成等边三角形(第一行一个点,第二行两个点,第三行三个点......),则整数 n 被称为三角形数,例如:

正方形数:对于整数 n,如果可以将 n 个点整齐排列成正方形(行数等于列数),则整数n被称为正方形数,例如:

题目描述:

对于任意一个正方形数,都可以由两个三角形数相加得来。 例如:
对于正方形数 9,可以由三角形数 3 和 6 相加得来:

给定 n 个整数,请判断其中有多少个正方形数,并且对于每个正方形数,求解其可以由哪两个三角形数相加得来。
例如:n = 4,4 个整数分别是 4、11、16、22。其中能构成正方形数的有4 和16。其中 4 可以由三角形数 1 和 3 相加得来,16 可以由三角形数 6 和 10 相加得来。

输入格式

第一行输入一个整数 nn
第二行输入 nn 个整数,整数之间以一个空格隔开。

输出格式

第一行输出一个整数 mm,表示输入的整数中正方形数的个数。
接下来输出 mm 行:按输入顺序,对每个正方形数输出两个整数,表示对应的两个三角形数,要求小数在前、大数在后,两个整数之间以一个空格隔开。

样例输入输出

样例输入1

4
4 11 16 22

样例输出1

2
1 3
6 10

数据范围与测试点说明

  • 1n1051\le n\le 10^5
  • 44\le 每个整数 1018\le 10^{18}

时间限制与内存限制

  • 时间限制:11
  • 内存限制:10241024 KiB