題目 1074 對稱平方數：枚舉與回文判斷的高效解法

題目大意

找出所有不超過 255 的整數 i，使得 i*i 是回文數（正讀反讀相同）。無輸入，直接輸出滿足條件的 i，每行一個。

解法分析

1. 範圍極小，暴力枚舉即可

i ∈ [0, 255]，i*i ≤ 65025（5 位數）。直接平方、轉字符串判回文，時間可忽略。

2. 無字符串純數學判斷（教學用）

按位數分類：
• 1 位：n < 10 全部回文
• 2 位：n % 10 == n / 10
• 3 位：n % 10 == n / 100
• 4 位：n % 10 == n / 1000 && (n%1000-n%10)/10 % 10 == ((n%1000-n%10)/10)/10
• 5 位：n/10000 == n%10 && (n%10000-n%10)/10 /100 == (n%10000-n%10)/10 %10

3. 更優雅的通用回文判斷

bool isPalindrome(int x) {
    if (x < 0) return false;
    int orig = x, rev = 0;
    while (x) { rev = rev * 10 + x % 10; x /= 10; }
    return orig == rev;
}

完整代碼 (C)

#include <stdio.h>
bool isPal(int n) {
    int o = n, r = 0;
    while (n) { r = r * 10 + n % 10; n /= 10; }
    return o == r;
}
int main() {
    for (int i = 0; i < 256; ++i)
        if (isPal(i * i))
            printf("%d\n", i);
    return 0;
}

輸出結果

0
1
2
3
11
22
26
101
111
121
202
212
264

共 14 個數（含 0）。若題目要求正整數，去掉 0 剩 13 個。

複雜度

• 時間：O(256 * log(65025)) ≈ 微秒級
• 空間：O(1)

延伸思考

• 若上限擴大到 10^9，需生成回文數再開方判斷，而非枚舉平方。
• 回文平方數序列：OEIS A002779。