等式(数论/唯一分解定理)
给定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的情况); 代码如下:
#includeint 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; }