NYOJ-476谁是英雄,分解质因子求约数个数！

谁是英雄

时间限制：1000 ms | 内存限制：65535 KB

难度：3

描述

十个数学家(编号0-9)乘气球飞行在太平洋上空。当横越赤道时，他们决定庆祝一下这一壮举。于是他们开了一瓶香槟。不幸

的是，软木塞在气球上打了一个洞，氢气泄漏，气球开始下降，眼看就要落入海中，所有人将要被鲨鱼吃掉。

但是尚有一线生机--若其中一人牺牲自己跳下去的话，那他的朋友们还能多活一会儿。但仍然有一个问题存在--谁

跳下去？所以他们想了一个非常公平的办法来解决这个问题--首先，每人写一个整数ai；然后计

算出a1×a2×a3×a4×……×a10的积的约数的个数N。例如，6的约数有4个（1、2、3、6），则N为4。这位牺牲自

己的英雄将由N的个位数来决定（编号为N的个位数的人要跳下去）。你的任务是求出N。

输入

T(T<=10)组测试数据。

十个整数ai(1≤ai≤10000)。

输出

N的个位数

样例输入

1

1 2 6 1 3 1 1 1 1 1

样例输出

其实以前做过类似求乘积的约数个数，很明显乘积会超范围，肯定是要从因子入手的，于是百度百科了一下“约数个数定理”，就知道有快速方法，只不过要先求出质因子个数，假如其乘积的质因子a1,a2,a3,a4...ak的个数分别是p1,p2,p3...pk，那么约数个数sum=(p1+1)(p2+1)(p3+1)....(pk+1);这便是约数个数定理；数据范围是10000，只有10个数，所以可以暴力分解质因数然后求出每个质因数的个数即可；

下面提供两种代码：

1.0 先打个10000的素数表，因为这10个数每个数都要分解质因子，只需将每个数分别分解（怎么分解请看代码）：

using namespace std;

const int N=10000+10;

int k,b[N],s[N],a[N]

void init()

{

    k=0;

    memset(b,-1,sizeof(b));

    memset(s,0,sizeof(s));//将10000内的素数储存起来，分解的时候直接除以素数；

    b[0]=b[1]=0;

    for(int i=2; i<=N; i++)

        if(b[i])

        {

            s[k++]=i;

            if(i>N/i) continue;

            for(int j=i*i; j<=N; j+=i)

                b[j]=0;

        }

}

int main()

{

    int t,x,i,j;

    init();

    scanf("%d",&t);

    while(t--)

    {

        memset(a,0,sizeof(a));//存每个质因子出现的次数；

        int f=1;

        for(i=1; i<=10; i++)

        {

            scanf("%d",&x);

            if(x==1)

                continue;

            else//分解质因数；

            {

                f=0;

                for(j=0; j<k; j++)

                {

                    while(x%s[j]==0)//注意一直除下去；

                    {

                        x/=s[j];

                        a[s[j]]++;//质因子出现的次数；

                    }

                    if(x==1) break;

                    if(b[x])//如果x本身就是素数了再加起来；比如：6/2=3;

                    {

                        a[x]++;

                        break;

                    }

                }

            }

        }

        if(f)//如果10个数全部是1则输出1；

        {

            printf("1\n");

            continue;

        }

        else

        {

            int sum=1;

            for(i=0; i<k; i++)//这里查找就方便一点；

                if(a[s[i]])

                    sum*=(a1[s[i]]+1);

            printf("%d\n",sum%10);//千万注意取个位数，题意描述不清，不然此代码一遍过；

        }

    }

    return 0;

}

2.0 原理和上面一样，只不过内存少了一点吗，就是基于数据个数和范围都较小，所以分解质因子的时候暴力分解：

using namespace std;

const int N=10000+10;

int b[N],a[N];

int main()

{

    int t,x,i,j;

    scanf("%d",&t);

    while(t--)

    {

        memset(a,0,sizeof(a));

        for(i=1; i<=10; i++)

        {

            scanf("%d",&x);

                for(j=2; x!=1&&j<=10000; j++)//分解质因数；

                    if(x%j==0)

                    {

                        x/=j;

                        a[j]++;

                        j--;//这里和上面那个while()含义一样，

                    }

        }

            int sum=1;

            for(i=0; i<10000; i++)//这里查询就比较慢了，很多都不是素数况且没有出现过；

                if(a[i])

                    sum*=(a[i]+1);

            printf("%d\n",sum%10);

    }

    return 0;

}

巴特西

NYOJ-476谁是英雄,分解质因子求约数个数！

谁是英雄

最新文章

热门文章