UVA 12009 Avaricious Maryanna：自守數構造與高精度模擬算法

題目大意

給定 n (≤500)，求 n 位數 x 使得 x² 的前 n 位等於 x。即 x² ≡ x (mod 10ⁿ)。這類數稱為自守數。

數學規律發現

• 1 位：0, 1, 5, 6
• 2 位：25, 76
• 3 位：376, 625
• 4 位：9376, 0625 (前導零視為 3 位)
• 規律：除 0,1 外，每位數解由前一位解擴展一位得到，且只有兩條鏈：...5 和 ...6

核心遞推公式推導

設 k 位解為 x，求 k+1 位解：新數 = a·10ᵏ + x (a∈0..9)

(a·10ᵏ + x)² = a²·10²ᵏ + 2a·10ᵏ·x + x²
模 10ᵏ⁺¹ 意義下：
≡ (x² mod 10ᵏ⁺¹) + 2a·x·10ᵏ  (因 10²ᵏ 被模掉)
第 k+1 位 = (x² / 10ᵏ) % 10 + 2a·(x % 10)  (mod 10)
令等於 a，枚舉 a=0..9 即可求解

完整 C 代碼實現

#include 
#include 

int t, n;
char a[505], b[505];  // 存儲兩條鏈：...5 和 ...6
int ans[505], num[505];

// 高精度平方，返回第 len 位數字 (0-indexed)
int cal(char *str) {
    memset(ans, 0, sizeof(ans));
    int len = strlen(str);
    for (int i = len-1; i >= 0; i--) num[len-i-1] = str[i]-'0';
    for (int i = 0; i < len; i++)
        for (int j = 0; j < len; j++)
            if (i+j < len) ans[i+j] += num[i]*num[j];
    for (int i = 0; i < len; i++) {
        ans[i+1] += ans[i]/10;
        ans[i] %= 10;
    }
    return ans[len];  // 返回第 len 位 (即新增位)
}

void init() {
    a[500] = b[500] = '\0';
    a[499] = '5'; b[499] = '6';  // 1位種子
    for (int i = 498; i >= 0; i--) {
        int aa = cal(a+i+1);
        int bb = cal(b+i+1);
        for (int j = 0; j < 10; j++) {
            if ((2*j*5 + aa) % 10 == j) a[i] = j+'0';
            if ((2*j*6 + bb) % 10 == j) b[i] = j+'0';
        }
    }
}

int main() {
    init();
    int cas = 0;
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
        printf("Case #%d:", ++cas);
        if (n == 1) printf(" 0 1 5 6\n");
        else {
            char *pa = a+500-n, *pb = b+500-n;
            if (*pa=='0' && *pb=='0') printf("Impossible\n");
            else if (*pa=='0') printf(" %s\n", pb);
            else if (*pb=='0') printf(" %s\n", pa);
            else {
                if (strcmp(pa, pb) < 0) printf(" %s %s\n", pa, pb);
                else printf(" %s %s\n", pb, pa);
            }
        }
    }
    return 0;
}

算法複雜度分析

優化說明：實際運行中 cal() 內層循環可優化至 O(len²)，500 位預處理約 1-2 秒，符合競賽限制。若需更快可用 FFT 加速乘法或預計算好答案表。

關鍵技術點總結

1. 自守數性質：僅存在兩條無限鏈（以 5/6 結尾）加上 0,1
2. 高精度乘法模擬：數組模擬豎式乘法，只需計算關鍵位
3. 從低位向高位構造：字符串逆序存儲，索引即位權
4. 前導零處理：結果可能以 0 開頭，輸出時保留

延伸知識

自守數在 10 進制中只有 4 個無限序列：...0, ...1, ...5, ...6。其他進制也有類似性質。此題考察數論洞察力 + 高精度實現能力 + 預處理優化思想。