UVA 128 - Software CRC

給出一串字符串,求其循環冗余校驗碼.

求法:把整個字符串看成一個整數m,第一個字符作為這個整數的最高字節,第二個字符作為次高字節,etc...

要求在這個整數最後加上兩個字節變成m2，使其整除34943.

解法:快速冪取模,粒度為一個字節.

#include 
#include 
using namespace std;
#define MOD 34943
char message[1025];

int mod_pow(int a, int b, int c){
	int res = 1, t = a;
	while(b){
		if(b & 1)res = res * t % c;
		t = t * t % c;
		b >>= 1;
	}
	return res % c;
}


int main(){
	while(gets(message)){
		if(message[0] == '#' && message[1] == 0)break;
		int ans = 0, len = strlen(message), shift = 2;
		for(int i = len - 1; i >= 0; --i){
				ans = (ans + message[i] * mod_pow(256, shift, MOD) % MOD) % MOD;
				shift++;
		}
		ans = (MOD - ans) % MOD;
		printf("%02X %02X\n", ans >> 8, ans & ((1 << 8) - 1));
	}
	return 0;
}