- 首页 > it技术 > >
给出n求1/n=1/x+1/y（n,x,y=1,2,3...）的解的个数,
#include
using namespace std;
/*
题意：给出n，求1/n=1/x+1/y（n,x,y=1,2,3...）的解的个数,找出最小的n，构成1/n的式子超过1000设x=n+a,y=n+b,化简可得n^2=a*b.设n^2的因子个数为p,n^2的所有因子中除n外都是成对出现的，故方程解数为(p+1)/2。
比如n=4,则x=8,y=8；x=20,y=5；x=12,y=6 一共有3种情况
一个数的约数必然包括1及其本身。
因为n <= 10^9，则n^2是一个很大的数，在时间和空间上都不允许直接操作，考虑到任何整数n都可以表示为 n = p1^e1*p2^e2*..pn^en，其中p1,p2..,pn都为素数,
并且n的约数个数为 (1+e1)*(1+e2)*...(1+en)；
所以n^2 = (p1^e1*p2^e2...pn^en)^2 = p1^2e1*p2^2e2...*pn^2en,故其约数个数为（1+2e1)*(1+2e2)*...(1+2en)；
所以只需求出n的约数个数即可，每次求出ek(k=1,2,3,4..)的时候，将结果乘上2即可。
//除不尽，说明n是大于sqrt(10^9)的素数，ret *= (1 + 2*1);
是正整数，则形如
n=p⑴^β⑴·p⑵^β*⑵·…·p(k)^β（k)
的数都是n的约数，其中β⑴可取a⑴+1个值：0,1,2，…，α⑴；β⑵可取α⑵+1个值：0,1,2，…，α⑵…；β（k）可取a(k)+1个值：0,1,2，…，α（k).且n的约数也都是上述形式，根据乘法原理，n的约数共有
（α⑴+1）（α⑵+1）…（α（k)+1)
*/int getCount(int n)
{
int p = 0;
vector temp(1009,0);
//for(int i = 2;
i * i <= n;
++i)
for(int i = 2;
i <= n;
++i)
{
if(n%i == 0)
{
while(n % i == 0)
{
++temp[p];
n /= i;
}
++p;
}
}
//if(n != 1) //除不尽，说明n是大于sqrt(10^9)的素数，ret *= (1 + 2*1);
//{
//++temp[p];
//++p;
//}
for(int i = 0;
i < p;
++i)
temp[i] *= 2;
int ans = 1;
for(int i = 0;
i < p;
++i)
ans *= (temp[i] + 1);
return (ans+1)/2;
}
int main()
{
int n;
cin >> n;
cout<< getCount(n) << endl;
return 0;
}
推荐阅读
