### 有指數和底數的範本 <div class="flex">   </div> ----  --- $2^{k} = n_0^2 + n_1^2 + n_2^2 + n_3^2$ 且 $n_0 \leq n_1 \leq n_2 \leq n_3$ 有 $n_0$ ~ $n_3$ 總共 4 個數字要挑選 ---- ``` cpp int num[4] = {}; int solutions = 0; // // pick() 每個位置挑選數字 // remain: 還剩多少可以分 // id: 哪一個位置在挑 0 ~ 3 // void pick(int remain, int id) { } ``` --- - 遞迴終止條件：已經在挑 $n_3$ 了，不需要再往下遞迴 - 檢查是否有解 - $n_0$ ~ $n_2$： $n_i$ 由前一個位置的數字($n_{i-1}$)開始，一直挑到這個位置的上限 - 依順序挑選一個數字 - 然後叫下一個位置起來挑 ---- ``` cpp 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_3$ 不用挑，前面挑剩的全都給它。輪到 $n_3$ 的時候，剩下要湊的數字，剛好是某個整數的平方的話，這時候就有答案。 ``` cpp if (id == 3) { // 換 n3 挑數字 int r = sqrt(remain); if (r*r == remain) { // 有解 // ... } return ; } ``` --- ## 每個位置挑數字的下限 $n_0 \leq n_1 \leq n_2 \leq n_3$ 所以 - $n_1$ 的下限就是 $n_0$，從 $n_0$ 目前挑中的數字開始往後挑 - $n_2$ 的下限就是 $n_1$，從 $n_1$ 目前挑中的數字開始往後挑 ---- 等等，那 $n_0$ 呢？就找最小的正整數 `1` 當代表囉！ ---- ```cpp if (id > 0) lbound = num[id-1]; else lbound = 1; ``` --- ## 每個位置挑數字的上限 對 $n_0$ 來說，它的最大值會發生在 $n_0 = n_1 = n_2 = n_3$ 的時候 $2^k = remain_0 = n_0^2 + n_0^2 + n_0^2 + n_0^2 = 4n_0^2$ => $n_0^2 = {remain_0 \over 4}$ => $n_0 = \sqrt{remain_0 \over 4}$ ---- $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_1^2 + n_1^2 = 3n_1^2$ => $n_1^2 = {remain_1 \over 3}$ => $n_1 = \sqrt{remain_1 \over 3}$ ---- $remain_0 - n_0^2 - n_1^2 = remain_2 = n_2^2 + n_3^2$ 同理 $n_2 = \sqrt{remain_2 \over 2}$ ---- ```cpp ubound = sqrt(remain/(4-id)); ``` --- ## 加速 逾時了！！  ---- 原因：需要反覆計算某數的平方   ---- 解方：在程式一開始時預先將平方數建表，改用查表法 ---- ``` cpp 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; } ``` ---- ``` cpp 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); } } ``` --- ## 神奇的巧合 試著執行看看，好像有規律 ... |k||k|| |-|-|-|-| |1|0|7|0| |2|1 1 1 1|8|8 8 8 8| |3|0|9|0| |4|2 2 2 2|10|16 16 16 16| |5|0|11|0| |6|4 4 4 4|12|32 32 32 32|