题意:等式 1 / x + 1 / y = 1 / n (x, y, n ∈ N+ (1) 且 x <= y) ,给出 n,求有多少满足该式子的解。(1 <= n <= 1e9)

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1299

分析:x,y肯定都满足 n<x<=y; 设 x = n + k; 带入上式得 :1/y = k/(n+n*k); 即 k要整除 (n+n*k); 又 k 一定整除 n*k; 即求 k 整除 n; 即求 n 的因数个数。

注意:   1.数据范围太大,不能直接分解n。

2.利用唯一分解定理的推论求因数个数:对于一个数n,由唯一分解定理得x=a1^k1*a2^k2...*an^kn.(ai为素数)。

则x的因子个数为(k1+1)*(k2+1)*...*(kn+1)。

    3.推出:x=(a1^k1*a2^k2......*an^kn). 则 n的因子个数为 (2*k1+1)*(2*k2+1)*......*(2*kn+1)。

    4.又x<=y, 则 ans=(ans+1)/2;(ans是n^2的因数个数)。

代码:

 #include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
using namespace std;
#define ll long long
#define mx 100000
int prime[mx];
int vis[mx];
void getprime()
{
int m=sqrt(mx+0.5);
for(int i=;i<=m;i++)
{
if(!vis[i])
{
for(int j=i*i;j<mx;j+=i)
vis[j]=;
}
}
int cnt=;
for(int i=;i<mx;i++)
if(!vis[i])
prime[cnt++]=i;
}
int fun(int num)
{
int ans=;
int qs=sqrt(num+0.5);
//cout<<qs<<endl;
for(int i=;prime[i]<=qs;i++) //设a=n+x,b=n+y。得到n^2=x*y
{
int cnt=;
while(!(num%prime[i])&&num>)
{
num/=prime[i];
cnt++;
}
ans*=(*cnt+); //注意:由于n的范围比较大,所以我们不能直接将n^2分解,
} //我们可以通过分解n从而得知n^2分解的情况,由此计算答案
if(num!=)
ans*=;
return ans;
}
int main()
{
getprime();
int t;
scanf("%d",&t);
for(int k=;k<=t;k++)
{
int n;
scanf("%d",&n);
int ans=fun(n);
printf("Scenario #%d:\n%d\n\n",k,(ans+)/);
}
return ;
}
05-04 07:50