ZeroJudge 解題筆記：c102. 00128 - Software CRC

作者：王一哲
日期：2026年3月4日


ZeroJudge 題目連結：c102. 00128 - Software CRC

解題想法

這題會用到字元的 ASCII 編碼，因為編碼為 0 到 255 的整數，可以用 1 個位元組 (byte)、8 個位元 (bit)、2 位數的 16 進位整數表示。題目的意思應該是將讀到的字串，逐一按照字元的 ASCII 編碼排成很長一列的 16 進位整數，最後再加上兩個 16 進位整數的 CRC 碼，讓這個很長的 16 進位整數可以被指定的 10 進位整數 34943 整除。題目要求的就是每一行測資對應的 CRC 碼。解題過程如下：

1. 假設字串對應的整數儲存於變數 m，從字串 s 最前面依序讀取字元 c，將 m 向左平移 8 位元之後加上 c 的 ASCII 編碼。為了避免 m 溢位，可以在每一次計算後對 g 取餘數。
2. 將 m 向左平移 16 位元，增加給 CRC 碼的空間，再對 g 取餘數 r。
3. 如果 r 等於 0，CRC 碼就是 0；反之，CRC 碼為 g-r。
4. 將 CRC 碼向右平移 8 位元再與 0XFF 取 &，可以得到第一個 byte 的值；將 CRC 碼與 0XFF 取 &，可以得到第二個 byte 的值。

Python 程式碼

使用時間約為 7 ms，記憶體約為 2.8 MB，通過測試。

import sys

def solve(s):
    g, m = 34943, 0  # 取餘數用的除數，字串編碼對應的整數
    for c in s:  # 依序讀取 s 的字元 c
        m = ((m << 8) + ord(c)) % g  # m 向左平移 8 位元後加上 c 的 ASCII 碼，再取餘數
    m <<= 16  # m 向左平移 16 位元，增加給 CRC 碼的空間
    r = m%g  # m 對 g 取餘數
    crc = 0  # CRC  碼預設為 0
    if r > 0: crc = g-r  # 如果 r 大於 0，CRC  碼改成 g-r
    byte1 = (crc >> 8) & 0xFF  # CRC  碼向右平移 8 位元，與 0xFF 取 &
    byte2 = crc & 0xFF  # CRC  碼與 0xFF 取 &
    print(f"{byte1:02X} {byte2:02X}")  # 將兩個位元組用 16 進位輸出

for line in sys.stdin:
    line = line.rstrip()
    if line == "#": break
    solve(line)

C++ 程式碼

使用時間約為 1 ms，記憶體約為 320 kB，通過測試。

#include <iostream>
#include <iomanip>  // for setfill and setw
using namespace std;

void solve(string s) {
    const int g = 34943;  // 取餘數用的除數
    long m = 0;  // 字串編碼對應的整數
    for(char c : s) {  // 依序讀取 s 的字元 c
        m = ((m << 8) + c) % g;  // m 向左平移 8 位元後加上 c 的 ASCII 碼，再取餘數
    }
    m <<= 16;  // m 向左平移 16 位元，增加給 CRC 碼的空間
    int r = m%g, crc = 0;  // m 對 g 取餘數，CRC 碼預設為 0
    if (r > 0) crc = g-r;  // 如果 r 大於 0，CRC 碼改成 g-r
    int byte1 = (crc >> 8) & 0xFF;  // CRC 碼向右平移 8 位元，與 0xFF 取 &
    int byte2 = crc & 0xFF;  // CRC 碼與 0xFF 取 &
    // 輸出答案，uppercase 用大寫輸出，hex 用 16 進位輸出，setfill 設定字串太短時填入的字元，setw 設定輸出長度
    cout << uppercase << hex << setfill('0') << setw(2) << byte1 << " ";
    cout << uppercase << hex << setfill('0') << setw(2) << byte2 << "\n";
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    string line;
    while(getline(cin, line) && line != "#") solve(line);
    return 0;
}