分解完全平方数

题目描述:

一个正整数 n 分解为 m 个完全平方数的和。

当有多种方案时：

1）输出 m 最小时的分解方案。

2）若两种方案 m 相同，输出第一个数尽可能小的方案

3）若两种方案第一个数仍相同，输出第二个数尽可能小的方案，以此类推。

如: 

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

2）69 可分解为 1² + 2² + 8² 或 2² + 4² + 7² ，则结果为 69 =  1² + 2² + 8²

输入格式:

一个整数n

输出格式:

第一行输出分解方案。

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

样例输入:

样例1：
12

样例2：
69

样例输出:

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

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

提示:

n = int(input( ))
path = [[-1, -1]] * (n + 1)
q = [0] * n
vis = [False] * (n + 1)
head = 0
q[0] = n
tail = 1
vis[n] = True
while head < tail and q[head] != int(q[head]**0.5) ** 2:
    ____________________
    head += 1
    i = 1
    while i * i <= num:
        tNum = num - i * i
        if tNum > 0 and vis[tNum] == False:
            q[tail] = tNum
            tail += 1
            path[tNum] = [num, i]
            _________________________
        i += 1
m = 1
p = q[head]
s =  str(int(p**0.5))+"^2"
while path[p][0] != -1:
    m += 1
    s =  str(path[p][1])+"^2" + '+' + s
    p = path[p][0]
s = str(n) + "=" + s
print(s)
print( m )

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

---

来源: 2023.4温州三模