POJ 1047 Round and Round We Go 詳解

題目：判定給定字符串（2~60 位，含前導零）是否為「循環數」。定義：n 位數 X，若對任意 k=1..n，k×X 的數字序列是 X 的循環移位（首尾相連視為同一序列），則 X 為循環數。
輸入多行，每行一數，輸出 X is cyclic 或 X is not cyclic。

核心數學定理

定理：n 位數 X（允許前導零）是循環數 當且僅當 X × (n+1) = 99...9 (n 個 9)。
證明略：循環數本質是 1/p 的循環節（p 為質數），滿足 10ⁿ ≡ 1 (mod p) 且 n 為最小正周期。則 X = (10ⁿ-1)/p，故 X×(n+1) = 10ⁿ-1（當 p=n+1 時）。反之亦真。

算法：大整數乘法驗證

1. 讀入字符串 s，長度 n。
2. 計算 s × (n+1)（模擬手算乘法，字符串/數組存儲）。
3. 檢查結果是否全為 9，且長度為 n（或 n+1 但最高位為 0）。
4. 全 9 → cyclic，否則 not cyclic。

參考代碼 (C++)

#include <bits/stdc++.h>
using namespace std;

bool isCyclic(const string& s) {
    int n = s.size();
    vector a(n);
    for (int i = 0; i < n; ++i) a[i] = s[n-1-i] - '0'; // 低位在前
    int mul = n + 1;
    vector res;
    int carry = 0;
    for (int i = 0; i < n; ++i) {
        int prod = a[i] * mul + carry;
        res.push_back(prod % 10);
        carry = prod / 10;
    }
    while (carry) {
        res.push_back(carry % 10);
        carry /= 10;
    }
    // 檢查是否全為 9（忽略最高位可能的 0）
    for (int d : res) if (d != 9) return false;
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;
    while (cin >> s) {
        cout << s << (isCyclic(s) ? " is cyclic" : " is not cyclic") << '\n';
    }
    return 0;
}

關鍵測試用例

常見錯誤

• ❌ 忽略前導零："01" 是 2 位數，必須按 2 位處理（01×3=03≠99）。
• ❌ 乘法進位處理錯誤：最高位進位後可能多出一位，需檢查所有位均為 9。
• ❌ 用內建整型：60 位遠超 long long，必須模擬大整數乘法。

總結

POJ 1047 是一道「數學性質 + 大整數模擬」的題目。核心在於知道循環數判定定理：X × (n+1) = 10ⁿ - 1。掌握此定理，題目瞬間化歸為大整數乘法驗證。這也體現了數論知識在算法競賽中的巨大威力——將複雜的排列組合條件轉化為簡單的代數等式。