等式（数论/唯一分解定理）

输入描述:

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

输出描述:

输出符合该方程要求的解数。

首先明白一个定理：唯一分解定理（算数基本定理） 任何一个大于1的自然数 N,如果N不为质数，那么N可以唯一分解成有限个质数的乘积N=P1a1P2a2P3a3......Pnan，这里P1<P2<P3......<Pn均为质数，其中指数ai是正整数。这样的分解称为 N 的标准分解式。证明可以去网上搜；

                接下来有几个重要的推论：（1）一个大于1的正整数N，如果它的标准分解式为

那么问题就转换成求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;
}