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

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

Description

⼩杨有⼀个正整数 nn,⼩杨想将它拆分成若⼲完全平⽅数的和,同时⼩杨希望拆分的数量越少越好。

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

Input Format

第⼀⾏包含⼀个正整数 nn,含义如题⾯所⽰。

Output Format

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

18

2

Hint

样例解释

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

数据范围

子任务编号 数据点占比 nn
1 20%20\% 20\leq 20
2 40%40\% 1000\leq 1000
3 40%40 \% 105\leq 10^5

对于全部数据,保证有 1n1051 \leq n \leq 10^5

Source

GESP六级202409