3901 - 小杨和整数拆分
题目描述
小杨有一个正整数 n ，小杨想将它拆分成若干完全平方数的和，同时小杨希望拆分的数量越少越好。
小杨请你编写程序计算出总和为 n 的完全平方数的最少数量。
输入
第一行包含一个正整数 n，含义如题面所示。
输出
输出一个整数，代表总和为 n 的完全平方数的最少数量。
样例
输入
18
输出
2
说明
【数据范围】
对于全部数据，保证有 1 \le n \le 10^5 。
| 子任务编号 | 数据点占比 | n |
|---|---|---|
| 1 | 20\% | \le 20 |
| 2 | 40\% | \le 1000 |
| 3 | 40\% | \le 10^5 |
样例 1 解释
18=9+9=16+1+1其中最少需要 2 个完全平方数。
来源
GESP 9月认证 C++ 六级真题
标签
