← 返回题目

题库练习小杨和整数拆分

← 上一题下一题 →

A71633 | $小杨和整数拆分$

来源编程题

时间限制1s

内存限制512MB

通过 / 提交0/0

题目描述

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

输入格式

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

输出格式

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

输入输出样例

输入 #1

输出 #1

【数据范围】 对于全部数据，保证有 1 \le n \le 10^5 。 子任务编号数据点占比n120\%\le 20240\%\le 1000340\%\le 10^5样例 1 解释 18=9+9=16+1+1 其中最少需要 2 个完全平方数。

C++ 编辑器

输入

输出