PAT 1019 General Palindromic Number：任意進制回文判斷

題目描述

給定非負整數 N (≤ 10^9) 和進制 b (2 ≤ b ≤ 10^9)。判斷 N 的 b 進制表示是否為回文。輸出 Yes/No 及 b 進制數字序列（高位在前，空格分隔）。

算法邏輯

1. 特殊情況：N = 0 直接輸出 "Yes" 和 "0"。
2. 反覆取模 b 獲取低位數字，存入數組 (低位在前)。
3. 雙指針檢查數組是否回文。
4. 逆序輸出數組 (高位在前)。

代碼實現 (C++)

#include 
using namespace std;

int digits[100]; // 足夠大，log_2(1e9) < 30

bool isPalindromic(int len) {
    for (int i = 0, j = len - 1; i <= j; i++, j--)
        if (digits[i] != digits[j]) return false;
    return true;
}

void convert(long long n, long long b) {
    int len = 0;
    if (n == 0) { digits[len++] = 0; return; }
    while (n) { digits[len++] = n % b; n /= b; }
    // 此時 digits[0..len-1] 為低位在前
    // 判斷回文直接用雙指針
    // 輸出需逆序
    if (isPalindromic(len)) cout << "Yes\n"; else cout << "No\n";
    for (int i = len - 1; i >= 0; i--) {
        cout << digits[i];
        if (i) cout << ' ';
    }
    cout << endl;
}

int main() {
    long long n, b;
    while (cin >> n >> b) convert(n, b);
    return 0;
}

關鍵點

• N = 0 特判：0 在任何進制下都是 "0"，是回文。
• 進制 b 可高達 10^9，但數字個數極少 (log_b(N) ≤ 30)，數組大小 100 綽綽有餘。
• 取模得到的數字順序是低位在前，回文判斷直接雙指針比較 `digits[i]` 和 `digits[len-1-i]` 即可，無需額外反轉。
• 輸出時逆序遍歷數組。

示例

27 2 -> 11011 (回文) -> Yes / 1 1 0 1 1
121 5 -> 441 (非回文) -> No / 4 4 1