C語言數論經典：三平方和定理與正整數解枚舉優化

問題描述

給定正整數 num (≤10000)，求滿足 x²+y²+z² = num 且 1≤x≤y≤z 的整數解。若多解僅輸出字典序最小（即最小 x，再最小 y）。多組測試至 EOF。

數學背景：勒讓德三平方和定理

正整數 n 可表示為三平方和 ⇔ n 不能寫成 4ᵃ(8b+7) 形式。可用於快速判斷無解情況。

原始代碼：三層暴力枚舉

for x=1..√n
  for y=1..√n
    for z=1..√n
      if x²+y²+z²==n && x≤y≤z: 輸出並break

複雜度 O(n^{3/2})，n=10000 時約 10⁶ 次迴圈，勉強可接受但可大幅優化。

優化策略

1. 邊界收緊：x ≤ √(n/3), y ≤ √((n-x²)/2), z = √(n-x²-y²) 整數判斷。
2. 去除內層迴圈：固定 x,y 後，z² = n - x² - y²，直接判斷是否為完全平方數。
3. 預計算平方表：sq[i]=i*i，O(1) 查表替代乘法。

高效實現代碼

#include <stdio.h>
#include <math.h>
#include <stdbool.h>

int main() {
    int sq[101]; // 100²=10000
    for (int i=0; i<=100; i++) sq[i]=i*i;

    int n;
    while (scanf("%d", &n) == 1 && n>0 && n<=10000) {
        // 快速無解判斷：勒讓德條件
        int t = n;
        while (t%4==0) t/=4;
        if (t%8 == 7) { printf("No solution\n"); continue; }

        bool found = false;
        for (int x=1; x*x*3 <= n && !found; x++) {
            for (int y=x; x*x + y*y*2 <= n && !found; y++) {
                int rem = n - sq[x] - sq[y];
                int z = (int)(sqrt(rem) + 0.5);
                if (z >= y && sq[z] == rem) {
                    printf("%d %d %d\n", x, y, z);
                    found = true;
                }
            }
        }
        if (!found) printf("No solution\n");
    }
    return 0;
}

關鍵優化效果

• 迴圈次數從 ~10⁶ 降至 ~幾千次（x 至 57, y 至 70）。
• 平方表查表 + sqrt 整數判斷，無內層迴圈。
• 勒讓德條件預判無解，避免無效計算。

擴展：四平方和定理（拉格朗日）

任意自然數可表示為四個整數平方和。若需求四數解，可先減去一平方數轉化為三平方和問題，遞歸求解。