UVa-128, ZOJ-1164: Software CRC

問題概要

CRCを計算する。CRC自体はいろいろあるようだけど、問題文の定義では、元のメッセージMに2byte追加してM2とする。M2を定数g(given)で割ったあまりが0になるようにする。

解法

(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;
}