a118: 03-4-指數2^k的四個自然數平方和之所有表示法

int num[4] = {};
int solutions = 0;

//
// pick() 每個位置挑選數字
//     remain: 還剩多少可以分
//     id: 哪一個位置在挑 0 ~ 3
//
void pick(int remain, int id)
{

}

void pick(int remain, int id)
{
    if (id == 3) {    // 終止條件
        // 檢查是否有解，若有，印出一組答案
        // ... 略 ...
        return;
    }
    int ubound;    // 此位置挑數字的上限
    int lbound;    // 此位置挑數字的下限
    // ...計算 lbound, ubound ...
    // ...
    
    // 開始挑數字
    for (int n = lbound; i <= ubound; n++) {
        num[id] = n;
        pick(remain - n*n, id+1);
    }
}

等等，那 \(n_0\) 呢？就找最小的正整數 1 當代表囉！

if (id > 0)
    lbound = num[id-1];
else
    lbound = 1;

\(remain_0 - n_0^2 = remain_1 = n_1^2 + n_2^2 + n_3^2\)

\(n_0\) 挑了一個數字，輪 \(n_1\) 挑選的時候，還剩 \(remain_1\)，此時還有 3 個數字還沒挑，\(n_1\)的最大值會發生在 \(n_1 = n_2 = n_3\) 的時候

\(remain_1 = n_1^2 + n_2^2 + n_3^2 \geq n_1^2 + n_1^2 + n_1^2 = 3n_1^2\)

=> \(n_1^2 \leq {remain_1 \over 3}\)

=> \(n_1 \leq \sqrt{remain_1 \over 3}\)

\(remain_0 - n_0^2 - n_1^2 = remain_2 = n_2^2 + n_3^2 \geq n_2^2 + n_2^2 = 2n_2^2\)

同理 \(n_2 = \sqrt{remain_2 \over 2}\)

ubound = sqrt(remain/(4-id));

原因：需要反覆計算某數的平方

解方：在程式一開始時預先將平方數建表，改用查表法

int sq[65536] = {}, solutions = 0;

int main()
{
    for (int i = 1; i < 65536; i++)
        sq[i] = i*i;
    int k;
    cin >> k;
    solutions = 0;
    solve(1 << k, 0);
    if (solutions == 0)
        cout << solutions << '\n';
    return 0;
}

void solve(int remain, int id)
{
    if (id == 3) {
        int n = sqrt(remain);
        if (sq[n] == remain) {
            // 印答案
        }
        return;
    }
    // 計算 lbound, ubound ...
    // ...
    for (int n = lbound; n <= ubound; n++) {
        num[id] = n;
        solve(remain - sq[n], id+1);
    }
}