题目背景

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

题目描述

给定正整数 $n$，将它表示为若干完全平方数的和。请计算所需完全平方数的最少数量。

输入格式

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

输出格式

输出一行一个整数，表示最少需要的完全平方数个数。

18

2

数据范围与提示

• $1 \le n\le 10^5$。
• 部分数据满足 $n \le 20$ 或 $n \le 1000$。
• 样例中 $18=9+9$，最少需要 $2$ 个完全平方数。

来源

GESP 2024 年 09 月 C++ 六级 T1