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);
    }
}

if (id == 3) {    // 換 n3 挑數字
    int r = sqrt(remain);
    if (r*r == remain) {
        // 有解
        // ...
    }
    return ;
}

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

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);
    }
}