hdu 1299 Diophantus of Alexandria

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

求方程1/x+1/y=1/n的解的个数

分析：

1/x+1/y = 1/n 设y = n + k;

==>1/x + 1/(n+k)=1/n;

==>x = n^2/k + n;

因为x为整数，k就是n^2的约数。

/*Heal The World
There's a place in your heart
And I know that it is love
And this place could be much
Brighter than tomorrow
And if you really try
You'll find there's no need to cry
In this place you'll feel
There's no hurt or sorrow
There are ways to get there
If you care enough for the living
Make a little space
Make a better place
Heal the world
Make it a better place
For you and for me
And the entire human race
There are people dying
If you care enough for the living
Make it a better place
For you and for me
If you want to know why
There's love that cannot lie
Love is strong
It only cares of joyful giving
If we try we shall see
In this bliss we cannot feel
Fear od dread
We stop existing and start living
The it feels that always
Love's enough for us growing
So make a better world
Make a better place
Heal the world
Make it a better place
For you and for me
And the entire human race
There are people dying
If you care enough for the living
Make a better place for you and for me
And the dream we were conceived in
Will reveal a joyful face
And the world we once believed in
Will shine again in grace
Then why do we keep strangling life
Wound this earth' crucify its soul
Though it's plain to see
This world is heavenly
Be god's glow
We could fly so high
Let our spirits never die
In my heart I feel you are all my brothers
Create a world with no fear
Together we cry happy tears
See the nations turn
their swords into plowshares
We could really get there
If you cared enough for the living
Make a little space
To make a better place
Heal the world
Make it a better place
For you and for me
And the entire human race
There are people dying
If you care neough for the living
Make a better place for you and for me
Heal the world
Make it a better place
For you and for me
And the entire human race
There are people dying
If you care neough for the living
Make a better place for you and for me
Heal the world
Make it a better place
For you and for me
And the entire human race
There are people dying
If you care neough for the living
Make a better place for you and for me
There are pepole dying
If you care enough for the living
*/

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int maxn=1e7+5;
typedef long long LL;
bool prime[maxn];
int p[maxn/10];//素数
int k;//一共有多少个素数
int num[1000];//素因子的个数，注意这里不要开的太大，容易超内存
int cnt;//多少个素因子
void isprime()//素数筛
{
    k=0;
    LL i,j;//注意long long 
    memset(prime, true, sizeof(prime));
    for(LL i=2; i<maxn; i++)
    {
        if(prime[i])
        {
            p[k]=i;
            k++;
            for(j=i*i; j<maxn; j+=i)
            prime[j]=false;
        }
    }
}
LL fenjie(LL n)//素因子分解
{
    cnt=0;
    LL ans=1;
    memset(num, 0, sizeof(num));
    for(int i=0; p[i]*p[i]<=n&&i<k; i++)
    {
        if(n % p[i] == 0)
        {
            //fac[cnt]=p[i];
            while(n%p[i]==0)
            {
                num[cnt]++;
                n/=p[i];
            }
            cnt++;
        }
    }
    if(n>1)
    {
        //fac[cnt]=n;
        num[cnt++]=1;
    }
    for(int i=0;i<cnt;i++)//n*n的个数
        ans*=(2*num[i]+1);
    return ans;
}
int main()
{
    isprime();
    int m,cas=1;
    scanf("%d",&m);
    while(m--)
    {
        LL x;
        scanf("%lld",&x);
        printf("Scenario #%d:\n%lld\n\n",cas++,(fenjie(x)+1)/2);
    }
    return 0;
}