分解完全平方数

题目描述:

一个正整数 n 分解为 m 个完全平方数的和，当有多种方案时，输出m 最小时的分解方案。

如: 12 可分解为 12个 1²之和，4 个完全平方数之和 ( 3²+ 1²+ 1² + 1² ) 等，最少可分解为3个完全平方数之和 ( 2²+ 2²+ 2² ) ，则结果为 12 = 2²+ 2²+ 2²。

输入格式:

一个整数n

输出格式:

第一行输出分解方案。

第二行输出分解的最少项数。

样例输入:

样例1：
12

样例2：
69

样例输出:

样例1：
12=2^2+2^2+2^2
3

样例2：
69=1^2+2^2+8^2
3

提示:

n<=100, 000

一个整数转成字符串，to_string(  )函数。

如把 x = 123 转字符串 s，则 s = to_string( x )。

 

若方案有多个，输出前面尽量小的一种。

时间限制: 1000ms
空间限制: 256MB

---