题解 | 最少的完全平方数

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        if (isPerfectSquare(n)) {
            System.out.println(1);
        } else if (isTwoSquares(n)) {
            System.out.println(2);
        } else if (checkFourCase(n)) {
            System.out.println(4);
        } else {
            System.out.println(3);
        }
    }

    private static boolean isPerfectSquare(int num) {
        int sqrt = (int) Math.sqrt(num);
        return sqrt * sqrt == num;
    }

    private static boolean isTwoSquares(int n) {
        for (int a = 1; a * a <= n; a++) {
            int remain = n - a * a;
            if (isPerfectSquare(remain)) {
                return true;
            }
        }
        return false;
    }

    private static boolean checkFourCase(int num) {
        int n = num;
        while (n % 4 == 0) {
            n /= 4;
        }
        return n % 8 == 7;
    }
}

https://www.nowcoder.com/discuss/727521113110073344

思路：

1. isPerfectSquare方法：检查一个数是否为完全平方数。通过计算其平方根并平方后与原数比较来判断。
2. isTwoSquares方法：遍历所有可能的平方数a²，检查剩余部分n - a²是否为另一个平方数。
3. checkFourCase方法：检查n是否满足四平方和定理中的特殊情况，即形如4^k*(8m+7)。
4. 主方法：依次调用上述方法，根据检查结果输出最少完全平方数的个数。