题目1372:

平方求和

时间限制:1000ms
单点时限:1000ms
内存限制:256MB

描述

对于一个非负整数n，最少需要几个完全平方数，使其和为n？

输入

输入包含多组数据。对于每组数据：
第一行是n；如果n为-1，表示输入结束。(0 <= n <= 1000000001)

输出

针对每组数据，输出最少需要的完全平方数。

样例输入

3
4
5
-1

样例输出

3
1
2

解题:

一开始的思路：动态规划

结果：超空间

动态规划是很自然的想法，每个N都可能是一个平方a 和其它平方s的和组成，通过控制平方数a的大小，并利用之前已经得到的答案，选择其中的最小值作为N的答案。
但是很显然，1000000002*sizeof(short)远远超出了空间限制。
不过开始在没有别的好办法的情况下，我还是写了，至少得点基础分吧。

short *table = new short [max_n+1];
table[0]=0;
table[1]=1;
for(int i=2;i<=max_n;i++){
    short min_count=table[i-1]+1;
    for(int j=1;j*j<=i;j++){
        int new_count = table[i-j*j]+1;
        if(new_count<min_count)min_count = new_count;
    }
    table[i]=min_count;
}

苦思冥想后的意外收获：四方定理

一时间没想到好办法，用第一种方法打印了前1000个数的解。如图

220216164030306082.jpg

非常有规律啊，我不禁猜测可能最大的答案就是4。
然后按图索骥，我找到了

四方定理：
所有自然数至多只要用四个数的平方和就可以表示。

顺便贴一个证明：

http://planetmath.org/proofoflagrangesfoursquaretheorem

改进的思路：位运算

结果：超时间

有了四方定理，可以简化问题，只要不属于1、2、3，答案必定是4无疑。
然后考虑到空间不足。设计了新方案：
使用位运算，数字i能否被分解就由第i位来标记，1个、2个、3个平方和就需要三个变量，分别是once，twice，third

const int MAX_N = 1000000002;
class SpaceArray {
    public:
        bitset<MAX_N> once;//only for  query
        bitset<MAX_N> twice;
        bitset<MAX_N> third;
};

once时间复杂度： O（根号N）
twice需要once中标记为平方的位数，嵌套两次相加而得，时间复杂度为O(N)
third同理，需要once和twice里位数的和， O（N^(3/2)）

注：把3个变量once、twice、third封装到class里，是为了 new 这个class，这种调用方式是在堆中分配内存，可以很大；相反，直接使用是在栈中调用，会报错-栈空间不够。
顺便复习了一下堆栈的知识，可怜我半吊子的C++水平。

最终的解决

放弃把表里每个值都求出来的思路了，现在只考虑输入的这个N；
采用方法：求根后取整再平方和原值比较。

bool check1(int number) {//是否一个平方组成
    int a = int(sqrt(number));
    return a*a == number;
}
bool check2(int number) {//是否两个平方和组成
    for (int i = 1, i2 = i*i; i2<number; i2+=(2*i+1), i++) {
        if (check1(number - i2))return true;
    }
    return false;
}
bool check3(int number) {//是否三个平方和组成
    for (int i = 1, i2 = i*i; i2<number; i2 += (2 * i + 1), i++) {
        if (check2(number - i2))return true;
    }
    return false;
}

根据四方定理，不是以上三者的都属于4个平方和可以组成的。
3个函数求值的时间复杂度如下
O（1）
O（N^1/2）
O（N）