UVa-128, ZOJ-1164: Software CRC
解法
(M<<16+X)%g = 0なんだから、X=-(M<<16) (g)。これを先頭の文字列から計算していけば良い。
acceptされたコード
計算量O(strlen)。
#include <cstdio> #include <string> #include <iostream> using namespace std; const int g = 34943; int main(){ string line; while(getline(cin, line)){ if(line == "#"){ break; } const int L = line.length(); unsigned int ans = 0; for(int i=0; i<L; i++){ ans = ((ans<<8) + g - line[i]) % g; } ans <<= 16; ans %= g; printf("%02X %02X\n", ans>>8, ans&(0xff)); } return 0; }