链接：/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均为正整数）
输入描述:
在第一行输入一个正整数T。接下来有T行，每行输入一个正整数n，请求出符合该方程要求的解数。（1<=n<=1e9）
输出描述:
输出符合该方程要求的解数。
思路
1/x+1/y=1/n
–>
nx+ny=xy
–>
(x-n)*(y-n)=n*n
所以
temp=n * n ,
其实就是求 temp这个数<= n 的因子的个数
不能直接求 数据太大
分解质因子降低时间复杂度：
每个合数都可以写成几个质数相乘的形式，这几个质数就都叫做这个合数的质因数。如果一个质数是某个数的因数，那么就说这个质数是这个数的质因数。而这个因数一定是一个质数。
而分解质因子法求一个数的因子个数算法解析：如36，=1*2*2*3*3；设因子2的个数是n个，因子2可以生成n个因子（此例子是2,2*2=4）因子3的个数是m个，可以生成m个因数（3,9），而后生成的因子可以生成n*m个因子（即（2,4）和（3,9）的结合）。因为1也是其因子，所以总共的因数个数是n+m+n*m+1；=n*(m+1)+m+1=(n+1)*(m+1);所以把质因子个数求出来+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个}}}
如果觉得《等式（分解质因子求因子个数）》对你有帮助，请点赞、收藏，并留下你的观点哦！
