主題
題目連結：
題目大意：
輸入有多列，每列給定一字串（不超過 1024 個字元）。請輸出這個字串的 CRC 檢查碼。
CRC，即循環冗餘校驗（Cyclic Redundancy Check）。在此定義為：
我們定一個 g = 34943 ，藉此產生一個兩位元組（即 16 位元）的檢查碼。使其加到原字串的後方後，將該新字串視為一連串的二位數字（即看這個資料在記憶體的實際儲存位元之值）可以被 g 整除。
輸出為兩位元組的十六進位表示法，輸出格式參見範例輸出。
範例輸入：
this is a test
A
AB
Nothing gonna change my love for you.
#
範例輸出：
77 FD
00 00
0C 86
60 1B
57 98
解題思維：
利用餘數的性質（如這題的做法）——取餘的先後順序不影響最終餘數值（保證同餘）。
因此如果要求原字串之位元除以 34943 的餘數 R，我們可以掃過一次原字串，每碰到一個字元就把我們要的結果值（用一個變數表示，初始化值為 0）乘以 2 ^ 8 （因為一個字元佔 8 個位元），然後再加上該字元之值。再來將結果值除以 34943 取餘數，繼續到下一個字元。當字串掃完之後我們就得到了餘數值 R。
但是我們要求的是檢查碼之值，在此令其 = X 。而 X 的值是要接在原字串後面的，因此 R 與 X 會形成一個關係式 34943 | R × 2 ^ 16 + X ，其中 a | b 的符號代表 a 可以整除 b ，換句話說 b 可以「被」 a 整除。
由上式可以得到 R × 2 ^ 16 + X ≡ 0 (mod 34943)。移項後變為 -(R × 2 ^ 16) ≡ X (mod 34943)。
因此求出 -R × 2 ^ 16 取除以 34943 的餘數（即模 34943），而這邊會得出負的餘數值，只要加上 34943 就會變成正的（因為我們的 X 會是一個正數）。此時的餘數值即是 X 。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
