小杨和整数拆分
时间限制:1.0 s
内存限制:512.0 MB
题面描述
小杨有一个正整数n,小杨想将它拆分成若干完全平方数的和,同时小杨希望拆分的数量越少越好。
小杨请你编写程序计算出总和为n 的完全平方数的最少数量。
输入格式
第一行包含一个正整数n,含义如题面所示。
输出格式
输出一个整数,代表总和为n 的完全平方数的最少数量。
输入样例
18
输出样例
2
18=9+9=16+1+1,其中最少需要2 个完全平方数。
对于全部数据,保证有1≤n≤105。
复制链接后可在微信、QQ、小红书等平台粘贴分享;答案与解析在题目页。