给定n，求1/x + 1/y = 1/n （x<=y）的解数~hdu-1299~(分解素因子详解）

链接：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）

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

这题是我在牛客比赛时候遇到的一题，表示根本不会啊！
靠大佬点拨才能把问题转化为分解素因子。

第一步先要因式分解  y=（x*n)/(x-n); 设（x-n）=a;
y=(n*(a+n))/(a);
y=n+(n*n)/a;
问题终于转为为了求n^2的素因子
n^2的素因子是n的素因子数目的两倍 ，这个非常的显然。
还有一个步骤一个数的因子数为（每一个素因子的数目+1）相乘所得
例如15的因子数目为1，3，5 ，15  （1+1）*（1+1）=4；
还有最后一个小细节 ，一个数大于sqrt（n）素因子最多有且只有一个
因为求的是n^2的因数  所以 （2*1+1）=3；
才会有最后一句 if(n>1)  ans*=3;


菜是原罪！！！

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;


int main() {
    int t;
    scanf("%d",&t);
    while(t--) {
        int n,ans=1,m,temp=0;
        scanf("%d",&n);
        m=(int)sqrt(n);
        for(int i=2; i<=m; i++) {
            if(n%i==0) {
                while(n%i==0) {
                    n=n/i;
                    temp++;
                }
                ans=ans*(temp*2+1);
                temp=0;
            }
        }
        if(n>1)  ans*=3;
        printf("%d
",ans/2+1);
    }
    return 0;
}