HDOJ Problem - 1299

题意：等式 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 ;

 }