题目背景

2024 年 9 月 GESP C++ 六级编程第 1 题

题目描述

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

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

输入格式

第⼀⾏包含⼀个正整数 $n$，含义如题⾯所⽰。

输出格式

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

样例1

18

2

样例解释

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

数据范围

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