给定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
证明可以去网上搜；
接下来有几个重要的推论：
（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
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;
}
京公网安备 11010802041100号