hdu-1299 Diophantus of Alexandria(分解素因子)

思路：

因为x,y必须要大与n,那么将y设为(n+k);那么根据等式可求的x=(n²)/k+n;因为y为整数所以k要整除n*n;

那么符合上面等式的x,y的个数就变为求能被n*n整除的数k的个数，且k>=n;

那么k就在n到n*n之间，不过这样不则么好求。

因为x,y具有对称性，从y=(n+k)和x=(n²)/k+n;也可以看出（n*n/k,和k等价因为k*（n*n/k）=n*n）；

由于任何数都可以拆成素数的乘积，形式为a1^x1*a2^x2*a3*^x3......;

那么因数的个数为（1+x1）*（1+x2）*（1+x3）......,要求的是n*n,，n和n*n的素因子种类是相同的，所以n*n的因数个数为（1+2*x1）*（1+2*x2）*(1+2*x3).....;

那么求n*n的因数个数，只要求n的因数个数。

求因数个数就要先求素因数，求n的素因数打表就行了，素数打表只要打到1e5就行了，

因为在sqrt(n)之后如果要有n的素因数的话只会有一个因为如果有两个大与sqrt(n)的素因数那么设一个x1,另一个x2,就有x1*x2>n,

所以不可能有两个以上的且大于sqrt(n)的素因数。那么如果前面的素数中找完后，n还>1，那么此时n就是那个素因数，那么这对应素数的重复个数就为1。

关于因数个数（1+x1）*（1+x2）*（1+x3）......中1+xk表示的是第k个素因数能选的不同数量，那么乘起来就是不同的因数个数（1+x1）*（1+x2）*（1+x3）......了；

#include<stdio.h>
#include<algorithm>
#include<stdlib.h>
#include<string.h>
#include<iostream>
#include<math.h>
const int Y=1e5+3;
const int uu=1e5;
const int Z=1e4;
bool flag[Y];
int prime[Z];
using namespace std;
int main(void)
{
    int n,i,j,k,p,q;
    memset(flag,0,sizeof(flag));
    flag[0]=true;
    flag[1]=true;
    for(i=2; i<1000; i++)
    {
        if(!flag[i])
        {
            for(j=i; j*i<=uu; j++)
            {
                flag[i*j]=true;
            }
        }

    }
    int cnt=0;
    for(i=2; i<uu; i++)
    {
        if(flag[i]==false)
        {
            prime[cnt++]=i;
        }
    }//素数打表存0到1e5间的素数。
    cin>>k;
    {
        for(q=1; q<=k; q++)
        {
            cin>>p;
            int sum=1;
            for(i=0; i<cnt&&p>1; i++)
            {
                for(j=0; p%prime[i]==0; j++)
                {
                    p=p/prime[i];
                }//每个素因子的个数
                sum*=(1+2*j);
            }
            if(p>1)//特判，在1e5之后的p的素因子（最多一个）。
            {
                sum*=3;
            }
            cout<<"Scenario #"<<q<<":"<<endl;
            cout<<(sum+1)/2<<endl;//因为在x,y相等时只算了一次，所以要加1
            printf("
");
        }
    }
    return 0;

}