链接： https://www.nowcoder.com/acm/contest/90/F
来源：牛客网

题目描述

给定n，求1/x + 1/y = 1/n （x<=y）的解数。（x、y、n均为正整数）


输入描述:

在第一行输入一个正整数T。
接下来有T行，每行输入一个正整数n，请求出符合该方程要求的解数。
（1<=n<=1e9）

输出描述:

输出符合该方程要求的解数。
首先明白一个定理：唯一分解定理（算数基本定理）


            任何一个大于1的自然数 N,如果N不为质数，那么N可以唯一分解成有限个质数的乘积N=P1a1P2a2P3a3......Pnan，这里P1<P2<P3......<Pn均为质数，其中指数ai是正整数。这样的分解称为 N 的标准分解式。


证明可以去网上搜；



                接下来有几个重要的推论：


                 （1）一个大于1的正整数N，如果它的标准分解式为
 :
                        n=  p1^a1 * p2^a2 * p3^a3 * p4^a4 ......  * pk^ak
                         ，那么它的正因数个数为（1+a1）* (1+a2) * (1+a3) * (1+a4) * .......* (1+ak); 
                 
（2）此外还可证明根号2是 无理数等等。
（3）证明 素数个数无限。
        在本题中我们用的是推论一：                   我们设 n+a=x, n+b=y,带入等式化简后得n^2=a*b且b>=a; 
                   那么问题就转换成求n^2有多少对因子； 
                   可以用短除法可以将n分解p1^a1 * p2^a2 * p3^a3 * p4^a4 ......  * pk^ak(pi为质数)的形式。 
                   那么n^2=p1^(2*a1) * p2^(2*a2) * p3^(2^a3) * p4^(2*a4)  *..... * pk^(2*ak); 
                   可以推出n^2所有的因子个数sum为（1+2*a1）* (1+2*a2) * (1+2*a3) * (1+2*a4) * .......* (1+2*ak); 
                   所以结果为(sum+1)/2;     (sum+1是因为考虑到a==b==n的情况)；


代码如下：



#include<stdio.h>
int DecompositionFactor(int n);
/*
3
1
20180101
1000000000
输出

1
5
181
*/ 
int main()
{
	int t;
	
	scanf("%d",&t);
	
	while(t--)
	{
		int n;
		
		scanf("%d",&n) ;
		
		int sum = DecompositionFactor(n);    //求出n^2的所有因子的个数 
		
		printf("%d\n",(sum + 1) / 2);
		
	}
	
	
	
	
	return 0;
} 
int DecompositionFactor(int n)
{
	int sum = 1;
	
	for(int i = 2;i*i <= n;i++)
	{
		int count = 0;
		
		while(n%i == 0)
		{
			count++;
			
			n/=i;
		}
		
		sum *= (1 + 2 * count);
	}
	
	if(n != 1)
	sum *= (1 + 2 * 1);
	
	return sum;
}