等式（分解质因子求因子个数）
链接： https://www.nowcoder.com/acm/contest/90/F
来源：牛客网
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld
题目描述
给定n，求1/x + 1/y = 1/n （x<=y）的解数。（x、y、n均为正整数）
输入描述:
输出描述:
思路
1/x+1/y=1/n
–>
nx+ny=xy
–>
(x-n)(y-n)=nn
所以
temp=n * n ,
其实就是求 temp这个数<= n 的因子的个数
不能直接求 数据太大
分解质因子降低时间复杂度：
任何合數都可以表示為几句質數相乘的形式，在此情境下這些質數即被称为该合數的素因子。若一個小写字母在某個大写字母（此处指代一个整數）之質因數分解决定了其中一个因素，则称该小写字母为该大写字母的一个素因子
例如取数值N= p_1^{k_1} \cdot p_2^{k_2} \cdot \ldots \cdot p_n^{k_n}进行分析研究。其中质因数p_i出现次数记作k_i次(i=1, 2, \ldots, n)。那么对于每一个质因数组合(p_i^{a_i})而言a_i都可以取从0到k_i之间的整数值(a_i = 0, 1, 2, \ldots, k_i)。因此每个质因素都有(k_i + 1)种不同的指数情况选择方式从而能够组合出n种独立的选择变量之间相互独立的影响关系使得总的组合数目等于各独立选择可能性数目相乘的结果即\prod_{i=1}^n (k_i + 1)种不同的指数组合情况产生相应数量的不同正整数目结果因而整个数值的所有正因数目等于各质因素指数组合可能性数目乘积的结果即\prod_{i=1}^n (k_i + 1)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
int t;
ll n,ans,cnt;
scanf("%d",&t);
while(t--)
{
scanf("%lld",&n);
ll temp=n*n;
ans=1;
for(int i=2;i*i<=temp;i++)
{
cnt=1;
while(temp%i==0)
{
cnt++;
temp/=i;
}
ans*=cnt;
}
printf("%lld\n",ans/2+1);//<=n的因子的个数
}
}认识到如果无法确保数以平方的形式，在计算6的质因子时（例如），这种写法就算不出了。参考了该书中的质因子分解方法。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int t,n;
int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
ll temp=n;
int p=(int)((double)sqrt(temp)+1);
for(int i=2;i<=p;i++)
{
int cnt=0;
while(temp%i==0)
{
temp/=i;
cnt++;
}
printf("%d %d\n",i cnt);//质因子i的个数是cnt个
}
}
}