《技术》学考及选考相关问题请联系张博士13958083702(手机和微信同号) 问题 D: 最少数量

问题 D: 最少数量★★★

时间限制: 1 Sec  内存限制: 128 MB
提交: 195  解决: 143
[提交][状态][命题人:]

题目描述

给定一个正整数n(n<=1000),将正整数n分解成m个完全平方数之和,m最小等于几?比如n=5,5=12+12+12+12+12=22+12,则m最小等于2。

又比如12,可分解为12个1的平方之和; 也可以分解为3^2+1^2+1^2+1^2,  也可以分解为2^2+2^2+2^2,则结果为3

输入

输入一个正整数n,表示要被分解的数。

输出

输出一个整数m
样例输入
Copy
12
样例输出
Copy
3

提示

样例2输入

5

样例2输出

2

[提交][状态]

如有问题,请咨询客服
浙ICP备20001167号