2305.cpp

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

/*  This Code is Submitted by wywcgs for Problem 2305 on 2006-08-07 at 11:57:29 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

const int N = 32768;

bool prime[N];
int pn = 0, p[N];

int parse(int);

int main()
{
	int i, j, t, T;
	
	memset(prime, true, sizeof(prime));
	for(i = 2; i < N; i++) {
		if(!prime[i]) continue;
		p[pn++] = i;
		for(j = 2; i*j < N; j++) prime[i*j] = false;
	}
	scanf("%d", &T);
	for(t = 0; t < T; t++) {
		int n; scanf("%d", &n);
		printf("Scenario #%d:\n%d\n\n", t+1, parse(n));
	}
	
	return 0;
}

int parse(int n)
{
	int k = 1, i, m;
	for(i = 0; i < pn && n != 1; i++) {
		for(m = 0; n%p[i] == 0; m++) n /= p[i];
		k *= 2*m+1;
	}
	if(n != 1) k *= 3;
	return (k+1)/2;
}