Trailing Zeroes (I) LightOJ

题意就是给你一个数让你找它的正因子个数（包括自身，不包括1），这个地方用到一个公式，如果不用的话按正常思路来写会TL什么的反正就是不容易写对。

求任意一个大于1的整数的正因子个数

首先任意一个数n，n=P1^a1 * P2^a2 * P3^a3 *……Pn^an；

任意的整数n可以分解为m个素数ai次幂的连续乘机，这个地方解释不清自己再理解一下（Pi都为素数，依次往后pi越来越大，ai就是次幂，自己可以找几个任意整数n来套一下这个公式就会明白了）

然后正因子个数和：sum=（1+a1）*（1+a2）*（1+a3）……*（1+an）；

用这两个公式本题就可以轻松解决啦（这里还是不清楚的就套几个数就理解这两个公式了，是完全正确的哦）；

AC代码如下：

#include<stdio.h>

#include<string.h>

#include<math.h>

#include<algorithm>

using namespace std;

int pri[];

int tt[];

int s=;

void dabiao() //打个素数表会节省很多时间

{   int j;

    memset(tt,,sizeof(tt));

    tt[]=;

    tt[]=;

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

    {

        if(tt[i]!=)

        {

            pri[s++]=i;

            for(j=i+i;j<=;j+=i)

                tt[j]=;

        }

    }

    return ;

}

int main()

{

    int m,i,j,k,t,cas=;

    long long n,num,ans;

    scanf("%d",&t);

    dabiao();

    while(t--)

    {

        scanf("%lld",&n);

        num=;

        for(i=;i<s&&pri[i]*pri[i]<=n;i++)

        {

            ans=;

            if(n%pri[i]==)

            {

                while(n%pri[i]==)//此处就是来找素数的N次幂，存起来相乘来计算SUM

                {

                    ans++;

                    n/=pri[i];

                }

            }

        num=num*(ans+);

        }

            if(n>)//这个地方就不解释啦，自己想想咯

            num*=;

        printf("Case %d: %lld\n",++cas,num-);

    }

    return ;

}

巴特西

Trailing Zeroes (I) LightOJ - 1028

最新文章

热门文章