279. 完全平方数

发表于 更新于 分类于 本文字数： 109 阅读时长 ≈ 1 分钟

四平方定理:任何一个正整数都可以表示成不超过四个整数的平方之和。

推论：满足四数平方和定理的数，必定满足

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int numSquares(int n)
{
    if (n % 8 == 7)
        return 4;
    for (int i = n; i % 4 == 0;)
    {
        i /= 4;
        if (i % 8 == 7)
            return 4;
    }
    if (sqr((int)sqrt(n)) == n)
        return 1;
    for (int i = 1; sqr(i) <= n; i++)
    {
        if (sqr((int)sqrt(n - sqr(i))) == n - sqr(i))
            return 2;
    }
    return 3;
}