<style> img[alt ~= "bdr"] { border: 1px solid lightgrey; padding: 5pt} img[alt ~= "mh"] {max-height: 64%} div.flex {display: flex; justify-content: space-between;} div.flex.block { justify-content: center; align-items: center; color: #29292b; text-shadow: 0 0 3px #eee; background-color: rgba(255, 255, 0, 0.2); } .flex>p {margin: 0} .flex img:only-child {margin: 0} .flex.nmw img {max-width: none; max-height: none} div.big {font-size: 100pt} .center {text-align: center} .reveal section img {border: 1px solid #eee; background-color: transparent} .relative {position: relative} .absolute {position: absolute} .border {border: 3px solid red} .box {border: 3px solid red; position: absolute} table.celled td {border: 1px solid lightgrey;} table.celled tbody tr:last-child td {border-bottom: 1px solid lightgrey;} .reveal .slides { text-align: justify; } table#posinfo td { width: 170px; height: 170px; position: relative; text-align: center; } table#posinfo td span { position: absolute; left: 3pt; top: 3pt; font-size: 12pt; } </style> # a118: 03-4-指數2^k的四個自然數平方和之所有表示法 ---  ---- <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$ 來說： $2^k = remain_0 = n_0^2 + n_1^2 + n_2^2 + n_3^2 \geq n_0^2 + n_0^2 + n_0^2 + n_0^2 = 4n_0^2$ => $n_0^2 \leq {remain_0 \over 4}$ => $n_0 \leq \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_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}$ ---- ```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|