#G1071. [GESP202409 六级] 小杨和整数拆分

[GESP202409 六级] 小杨和整数拆分

[GESP202409 六级] 小杨和整数拆分

题目描述

小杨有一个正整数 nn,小杨想将它拆分成若干完全平方数的和,同时小杨希望拆分的数量越少越好。

小杨请你编写程序计算出总和为 nn 的完全平方数的最少数量。

输入格式

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

输出格式

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

样例 #1

样例输入 #1

18

样例输出 #1

2

样例解释

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

数据范围

子任务编号 数据点占比 nn
1 20% ≤20≤ 20
2 40% ≤1000≤ 1000
3 ≤105≤ 10^5
  • 对于全部数据,保证有 1≤n≤1051 ≤ n ≤ 10^5。

时间限制:1.0 s。内存限制:512.0 MB。