A71633. 小杨和整数拆分
编程题
入门
知识点
题目描述
小杨有一个正整数 n ，小杨想将它拆分成若干完全平方数的和，同时小杨希望拆分的数量越少越好。
小杨请你编写程序计算出总和为 n 的完全平方数的最少数量。
输入格式
第一行包含一个正整数 n，含义如题面所示。
输出格式
输出一个整数，代表总和为 n 的完全平方数的最少数量。
输入输出样例
输入 #1
18
输出 #1
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 个完全平方数。