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

題目大意

給定 n (1 ≤ n ≤ 500)，找出所有 n 位數 x，使得 x² 的前 n 位等於 x（即 x² ≡ x (mod 10^n)）。這類數稱為自守數。輸出所有解（升序），無解輸出 Impossible。

數學規律與構造法

• 除了 n=1 有 0,1,5,6，n>1 時解只有兩條鏈：...5 和 ...6。
• 設已知 k 位解 x，求 k+1 位解 a·10^k + x。
  由 (a·10^k + x)² ≡ a·10^k + x (mod 10^{k+1}) 推導得：
  a ≡ (x² / 10^k % 10 + 2·a·x) % 10 → a·(1 - 2x%10) ≡ (x²/10^k)%10 (mod 10)。
• 對 x 以 5 結尾：2x%10 = 0，方程變 a ≡ (x²/10^k)%10 (mod 10)，唯一解。
  對 x 以 6 結尾：2x%10 = 2，方程 a·(1-2) ≡ ... → -a ≡ ...，也唯一解。
• 因此可從 5, 6 迭代構造至 500 位。

高精度計算 x² / 10^k % 10

模擬豎式乘法，只需計算第 k+1 位（即 x² 的第 |x|+1 位）。

int cal(char* str) { // str 指向當前 x 的字串（低位在前）
    int len = strlen(str);
    static int num[505], ans[1010];
    for (int i = 0; i < len; i++) num[i] = str[len-1-i]-'0'; // 反轉存低位優先
    memset(ans, 0, sizeof(ans));
    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 位（0-index）即為 x² 的第 k+1 位
}

預處理 500 位答案

char A[505], B[505]; // A 以 5 結尾，B 以 6 結尾，低位在前
void init() {
    A[499] = '5'; B[499] = '6';
    for (int i = 498; i >= 0; i--) {
        int aa = cal(A+i+1), bb = cal(B+i+1);
        for (int d = 0; d < 10; d++) {
            if ((2*d*5 + aa) % 10 == d) A[i] = d+'0';
            if ((2*d*6 + bb) % 10 == d) B[i] = d+'0';
        }
    }
}

查詢輸出

int main() {
    init();
    int T; scanf("%d", &T);
    for (int cs = 1; cs <= T; cs++) {
        int n; scanf("%d", &n);
        printf("Case #%d:", cs);
        if (n == 1) { puts(" 0 1 5 6"); continue; }
        char* a = A + 500 - n;
        char* b = B + 500 - n;
        if (*a=='0' && *b=='0') puts(" Impossible");
        else if (*a=='0') printf(" %s\n", b);
        else if (*b=='0') printf(" %s\n", a);
        else {
            if (strcmp(a, b) < 0) printf(" %s %s\n", a, b);
            else printf(" %s %s\n", b, a);
        }
    }
}

關鍵點總結

1. 自守數只有兩條無限鏈（5 系、6 系），可逐位構造。
2. 高精度乘法只需求第 k+1 位，優化計算量。
3. 預處理 500 位，查詢 O(1) 切片輸出。
4. n=1 特判四個解 0,1,5,6。