题解 | 最少的完全平方数

#include <bits/stdc++.h>
using namespace std;

bool isSquare(long long x) {
    long long r = (long long)sqrtl((long double)x);
    return r * r == x;
}

int main() {

    long long n;
    cin >> n;

    // 1) 本身是平方
    if (isSquare(n)) {
        cout << 1 << '\n';
        return 0;
    }

    // 2) 两个平方之和
    for (long long a = 1; a * a <= n; ++a) {
        if (isSquare(n - a * a)) {
            cout << 2 << '\n';
            return 0;
        }
    }

    // 3) 判定是否必须为 4
    long long m = n;
    while (m % 4 == 0) m /= 4;
    if (m % 8 == 7) {
        cout << 4 << '\n';
        return 0;
    }

    // 4) 否则就是 3
    cout << 3 << '\n';
    return 0;
}