1069.cpp

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

/*  This Code is Submitted by wywcgs for Problem 1069 on 2005-10-28 at 12:50:45 */ 
#include <cstdio>
#include <cstring>

const int N_MAX = 3600;
const int MAX = 32768;

int main()
{
	int p[N_MAX], pn = 0;
	int q[MAX];
	bool prime[MAX] = {false}, print;
	int i, j, n, m, x, k;
	
	for(i = 2; i < MAX; i++) {
		if(!prime[i]) {
			p[pn++] = i;
			for(j = 2; i * j < MAX; j++) {
				prime[i*j] = true;
			}
		}
	}
	x = 1;
	while(true) {
		while(scanf("%d", &n) == 1) {
			if(n == 0) {
				return 0;
			} else {
				scanf("%d", &m);
				for(i = 0; i < m; i++) {
					x *= n;
				}
				if(getchar() == '\n') {
					break;
				}
			}
		}
		x--;
		memset(q, 0, sizeof(q));
		for(k = 0; x != 1; k++) {
			while(x % p[k] == 0) {
				x /= p[k];
				q[k]++;
			}
		}
		print = false;
		for(i = k; i >= 0; i--) {
			if(q[i] != 0) {
				if(print) {
					putchar(' ');
				}
				printf("%d %d", p[i], q[i]);
				print = true;
			}
		}
		putchar('\n');
	}
	
	return 0;
}