2110.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 2110 on 2005-10-09 at 14:29:34 */ 
#include <cstdio>
#include <cstring>
#include <cmath>
#define  MAX  1000000
#define  P_MAX  81000

class BitVector {
public:
	long c[32000];
	BitVector() {
		memset(c, 0, sizeof(c));
	}
	void set(long index) {    
		c[byteNumber(index)] |= mask(index);
	}
	bool test(long index) {
		int i = c[byteNumber(index)] & mask(index);
		if(i == 0) {
			return false;
		} else {
			return true;
		}
	}
	long mask(long index) {
		return 1 << (index % 32);
	}
	long byteNumber(long index) {
		return index >> 5;
	}
};

class BigInt {
public:
	unsigned long long num[16];
	void praseInt(char *s) {
		int len = strlen(s);
		int part = len / 7;
		int r = len % 7;
		int i, j;
		memset(num, 0, sizeof(num));
		for(i = 0; i < part; i++) {
			for(j = 0; j < 7; j++) {
				num[15-i] = num[15-i] * 10 + s[len-(i+1)*7+j] - '0';
			}
		}
		for(j = 0; j < r; j++) {
			num[15-part] = num[15-part] * 10 + s[j] - '0';
		}
	}
	bool equalsToZero() {
		int i;
		for(i = 0; i < 16; i++) {
			if(num[i] != 0) {
				return false;
			}
		}
		return true;
	}
	bool exactDiv(long n) {
		unsigned long long p = 0;
		int i;
		for(i = 0; i < 16; i++) {
			p = p * MAX * 10 + num[i];
			p %= n;
		}
		if(p == 0) {
			return true;
		} else {
			return false;
		}
	}
};

int main()
{
	BitVector *bv = new BitVector;
	BigInt *bi = new BigInt;
	long i, j, L, p;
	long prime[P_MAX], pnum = 0;
	char K[128];
	bool good;

	for(i = 2; i <= MAX; i++) {
		if(!bv->test(i)) {
			for(j = 2; i*j <= MAX; j++) {
				bv->set(i*j);
			}
			prime[pnum++] = i;
		}
	}
	while(scanf("%s %ld", K, &L) == 2) {
		bi->praseInt(K);
		if(bi->equalsToZero() && L == 0) {
			return 0;
		} else {
			good = true;
			for(i = 0; prime[i] < L && i < pnum; i++) {
				if(bi->exactDiv(prime[i])) {
					good = false;
					p = prime[i];
					break;
				}
			}
			if(good) {
				printf("GOOD\n");
			} else {
				printf("BAD %ld\n", p);
			}
		}
	}
	
	return 0;
}