[数论]hdoj 1299

题意

      给出一个数n(0<n<10^9)。问有多少种a，b的组合使得1/a+1/b=1/n。

思路

      第一步a,b肯定大于n。设a=n+x，b=n+y。得到n^2=x*y。题目转化为求n^2有多少种分解为两个数乘积的方法。

     第二步，这里有一个定理ai为一个质数。对于一个数字x，x=a1^k1*a2^k2,,,,,*an^kn。则x的因子个数为(k1+1)*(k2+1)*,,,,,*(kn+1)。

     第三步，容易推出x^2的因子个数为(2*k1+1)*(2*k2+1)*,,,,,*(2*kn+1)

     第四步，对于一个完全平方数x，其因子个数为n，则x=ab的组合的个数为(n+1)/2

 

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
const int nMax = 100000;
int sum[nMax] = {0};
int prime[nMax]={0};
void make(){
	int i,j;
	for(i=2;i<nMax;i++){
		if(i%2)sum[i]=1;
	}
	int temp=(int)sqrt(nMax);
	for(i=3;i<temp;i++){
		if(sum[i]){
			for(j=i+i;j<=nMax;j+=i){
				sum[j]=0;
			}
		}
	}
	sum[1]=0;sum[2]=1;
	int a=0;
	for(i=0;i<nMax;i++){
		if(sum[i]){
			prime[a]=i;
			a++;
		}
	}
}
int main(){
    int i,ans,b,c,n,tcs,tt;
    cin>>tcs;
    make();
    for(tt = 1; tt <= tcs; tt ++){
        cin>>n;
        ans = 1;
        b = sqrt(n);
        for(i = 0;prime[i] <= b; i ++){
            if(n % prime[i] == 0){
                c = 0;
                while(n%prime[i] == 0){
                    c ++;
                    n /= prime[i];
                }
                ans*=(c * 2 + 1);
            }
        }
        if(n != 1){
            ans *= 3;
        }
        printf("Scenario #%d:\n%d\n\n",tt,(ans+1)/2);
    }
    return 0;
}