题目描述

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


输入描述:

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

输出描述:

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

输入

3
1
20180101
1000000000

输出

1
5

181

1.先将等式通分化简 ，注意各值的取值范围2.可以得到 a * b = n * n ；即求n * n 的因子数，这里用到算术基本定理。（算术基本定理：一个大于1的正整数N，如果它的标准分解式为：  ，那么它的正因数个数为  啦啦啦）因此利用短除法可以得到注意：（1<=n<=1e9） 所以在求n后 sum *= （1 + 2 * ai).....sum 求的a , b 是其因子数而一对a,b的值为一组解， 考虑到a = b 的情况所以最后的答案（sum + 1)/2;

#include <stdio.h>
int main()
{
     int T , n;
     scanf ( "%d" , &T);
     while (T--)
     {
         scanf ( "%d" , &n);
         int ans = 0;
         int i = 2;
         int sum = 1;
         int flag = 0;
         if (n == 1)
         {
             sum = 1;
         }
         else
         {
             flag = 1;
         }
         while (n != 1)
         {
             while (1)
             {
                 if (n % i == 0)
                 {
                     ans++;
                     n = n / i;
                 //  printf("ans = %d n = %d i = %d\n" , ans , n , i);
                 }
                 else
                 {
                     break ;
                 }
             }
                 
                     sum *= (1 + 2 *ans); //注意我们要求的是n*n = a * b（n*n)的因子数 ， 而此时是n，因此为（1 + 2 * ans)
                 //  printf("sum = %d\n" , sum);
                 
                 ans = 0 ;
                 i++;
             
         }
         printf ( "%d\n" , (sum + 1)/2 ); //sum + 1 的原因是 有当a == b 的时候，原先的sum求的是a , b的个数而一对a*b是一个解，
         //因此需要除以 2；
     }
     return 0;
}