//题意：给出n，求1/n=1/x+1/y（n,x,y=1,2,3...）的解的个数
//解析：不妨设x>=y，有x=n+1,n+2,...n+k...,n+n;则y=(n*x)/(x-n);
//		则设k=x-n,易知k=1,2,3...n;故y=(n*n+n*k)/k,n*k%k=0,故原题
//		转化为求n*n的不大于n的因数个数。假如 n%p^c==0 && n%p^(c+1)!=0
//		p是质数，则n^2中，关于选择p的个数构成因数的情况有2*c+1种，
//		依次可求出n^2的因数个数，又要求因数<=n,则有(ans+1)/2,
//		ans为n^2的因数个数。n=1需要加一特判，暂时无法解释。

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN = 40007;
bool isprime[MAXN];
int prime[MAXN],tot;
void init() {
	fill(isprime,isprime+40000,true);
	for(int i = 3 ; i <= 200 ; i += 2 ) {
		if(isprime[i]) {
			int t = 40000/i;
			for(int j = 3 ; j <= t ; j += 2 ) {
				isprime[i*j] = false;
			}
		}
	}
	tot = 0;
	prime[tot++] = 2;
	for(int i = 3 ; i <= 39999 ; i += 2 ) {
		if(isprime[i])
			prime[tot++] = i;
	}
}
int solve(int n) {
	int ans = 1,t;
	for(int i = 0 ; prime[i]*prime[i] <= n && i < tot ; i ++ ) {
		t = 0;
		while(!(n % prime[i])) {
			t ++;
			n /= prime[i];
		}
		ans *= 2*t+1;
	}
	if(ans == 1 || n != 1)
		ans *= 3;
	return ans;
}

int main() {
	int t,n,var=0;
	scanf("%d",&t);
	init();
	while(t -- ) {
		scanf("%d",&n);
		int ans = solve(n);
		printf("Scenario #%d:\n",++var);
		if(n == 1) ans = 1;
		printf("%d\n\n",(ans+1)/2);
	}
	return 0;
}

• Re:推导过程及代码 (587) NENU08022 2010-06-05 08:58:11