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

小杨和整数拆分

em783947 程序题共个子题

题目描述

小杨有一个正整数 $n$，小杨想将它拆分成若干完全平方数的和，同时小杨希望拆分的数量越少越好。小杨请你编写程序计算出总和为 $n$ 的完全平方数的最少数量。

输入格式

第一行包含一个正整数 $n$，含义如题面所示。

输出格式

输出一个整数，代表总和为 $n$ 的完全平方数的最少数量。

样例

输入样例 1

输出样例 1

样例解释 1

18 = 9 + 9 = 16 + 1 + 1，其中最少需要 2 个完全平方数。

数据范围

子任务编号数据点占比 $n$

1 20% $\le 20$
2 40% $\le 1000$
3 40% $\le 10^5$

对于全部数据，保证有 $1 \le n \le 10^5$。

本题为编程题，提交代码并运行通过测试点后判分。

正在加载题目数据…

第空

已答 /

子题

第空

提示

该题型需在试卷/作业中作答，单题练习暂不支持

答案解析

提交记录

共条仅展示自由练习提交

正在加载提交记录…

讨论

发布

登录后参与讨论

立即登录

发布讨论需先绑定并验证手机号

去绑定手机号

加载中…

我

回复 @

发送

还没有人讨论，来发表第一条吧