1560.cpp

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

/*  This Code is Submitted by wywcgs for Problem 1560 on 2005-10-29 at 08:36:37 */ 
#include <cstdio>

const int MAX = 46500;
const int N_MAX = 12800;

int p[N_MAX], pn = 0;
bool prime[MAX] = {false};

int main()
{
	int i, j;
	int n, m, x;
	int fn, k, q;
	bool div;
	
	for(i = 2; i < MAX; i++) {
		if(!prime[i]) {
			p[pn++] = i;
			for(j = 2; i * j < MAX; j++) {
				prime[i*j] = true;
			}
		}
	}
	while(scanf("%d %d", &n, &m) == 2) {
		x = m;
		if(m == 0) {
			div = false;
		} else if(m <= n) {
			div = true;
		} else {
			div = true;
			for(i = 0; i < pn && m != 1; i++) {
				for(fn = 0; m % p[i] == 0; fn++) {
					m /= p[i];
				}
				k = n;
				for(q = 0; k != 0; k /= p[i]) {
					q += k / p[i];
				}
				if(fn > q) {
					div = false;
					break;
				}
			}
			if(m > n && n != 0) {
				div = false;
			}
		}
		if(div) {
			printf("%d divides %d!\n", x, n);
		} else {
			printf("%d does not divide %d!\n", x, n);
		}
	}
	
	return 0;
}