ACM 1006 Do the Untwist - 字符串解密還原

ZOJ 1006 Do the Untwist 題解：加密演算法逆向還原

本題給定加密後字符串 textC 與密鑰 k，要求還原明文 textP。加密規則明確：字符映射、位置置換、模 28 運算。

加密流程 (正向)

1. 字符編碼：'_'→0, 'a'~'z'→1~26, '.'→27
2. 對明文每位 i：codeP[i] = encode(textP[i])
3. 位置置換：j = (k * i) % len，codeC[j] = (codeP[i] + i) mod 28
4. 字符解碼：textC[j] = decode(codeC[j])

解密流程 (逆向)

已知 textC, k, len 求 textP：

1. codeC[i] = encode(textC[i])
2. 對每個密文位置 i，對應明文位置 j = (k * i) % len
3. 逆向模運算：codeP[j] = (codeC[i] - j) mod 28 (注意負數處理)
4. textP[j] = decode(codeP[j])

因 k 與 len 互質 (題目隱含)，映射 i → j 為排列，可唯一逆向。

關鍵代碼實現

#include 
#include 

#define MAXLEN 71

int len;

int encode_char(char c) {
    if (c == '_') return 0;
    if (c == '.') return 27;
    return c - 'a' + 1;
}

char decode_char(int v) {
    if (v == 0) return '_';
    if (v == 27) return '.';
    return v + 'a' - 1;
}

int mod28(int x) {
    x %= 28;
    return x < 0 ? x + 28 : x;
}

void untwist(char *textC, int k) {
    int codeC[MAXLEN], codeP[MAXLEN];
    char textP[MAXLEN];

    for (int i = 0; i < len; i++) codeC[i] = encode_char(textC[i]);

    for (int i = 0; i < len; i++) {
        int j = (k * i) % len;
        codeP[j] = mod28(codeC[i] - j);
    }

    for (int i = 0; i < len; i++) textP[i] = decode_char(codeP[i]);
    textP[len] = '\0';
    printf("%s\n", textP);
}

int main() {
    int k;
    char textC[MAXLEN];
    while (scanf("%d", &k) == 1 && k) {
        scanf("%s", textC);
        len = strlen(textC);
        untwist(textC, k);
    }
    return 0;
}

關鍵點詳解

1. 模 28 減法：codeP[j] = (codeC[i] - j) mod 28。C 語言 % 對負數結果為負，需修正為 [0,27] 區間
2. 位置映射逆向：加密時 j = (k*i)%len 將明文 i 映射到密文 j；解密時遍歷密文索引 i，計算對應明文索引 j，填入 codeP[j]
3. 互質保證：k 與 len 互質確保映射為雙射，否則解密不唯一
4. 字符集：26 小寫字母 + '_' + '.' 共 28 個符號

測試驗證

輸入:
5
c_abc
0
輸出:
abc_c

手動驗證：明文 abc_c (長度 5)，k=5。加密過程可反推得密文 c_abc。

複雜度

• 時間：O(len)，len ≤ 70 極快
• 空間：O(len)

常見錯誤

1. 模運算負數處理錯誤，導致字符映射越界
2. 位置映射方向搞反 (用 (k*i)%len 直接作為明文索引)
3. 未處理多組測試直到 k=0 終止
4. 字符編碼/解碼邏輯與題目定義不符 (如大小寫、符號順序)