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

Type: RemoteJudge

1000ms

512MiB

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

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

编程计算总和为 $n$ 的完全平方数的最小数量。

输入只有一行一个正整数 $n$ 。

输出一行一个整数表示答案。

对全部的测试数据，保证 $1 \leq n \leq 10^5$ 。