spoj阶乘(超过时间限制错误).我该如何改善我的解决方案? [英] spoj factorial (time limit exceeded error). How can i improve my solution?

问题描述

这是我在 spoj 上的问题的链接.

Here is the link to my question on spoj .

我已经尝试了递归和非递归地使用它.但是我收到了超过时间限制的错误消息.如何改善我的解决方案?

I have tried it using both recursively as well as non recursively. But I am getting time limit exceeded error. How can I improve my solution?

我已经在下面显示了两种解决方案.

I have shown both the solutions below.

A)非递归方法.

#include <stdio.h>

int main()
{
    long long int t,n,i,j=0,y;    
    unsigned long long int fact;

    scanf("%lld",&t);    
    i=t;

    while(i>0)      
    {       
        scanf("%lld",&n);        
        fact=1;

        for(y=1;y<=n;y++)            
              fact=fact*y;

        j=0;

        while(fact%10==0)          
              j++;

        printf("\n%lld",j);        
        i--;         
      }

    return 0;
}

B)非递归

#include <stdio.h>

unsigned long long int fact(long long int);

int main() 
{      
      long long int t,n,i,j=0;      
      unsigned long long int y;

      scanf("%lld",&t);      
      i=t;

      while(i>0)       
      {

           scanf("%lld",&n);        
           y=fact(n);        
           j=0;

           while(y%10==0)          
                 j++;

           printf("\n%lld",j);

           i--;

         }

   return 0;    
}


unsigned long long int fact(long long int m) 
{  
   if(m==0)    
        return 1;

    else       
         return (m*fact(m-1));

}

推荐答案

问题将减小为n中10的次幂！ (n的阶乘)，但是为此我们必须找到2和5的幂，因为10素数分解为2和5

Problem reduces to this find power of 10 in n! (factorial of n), but for that we have to find power of 2 and 5 , as 10 prime factorizes into 2 and 5

k1= [n/2] + [n/4] + [n/8] + [n/16] + ....
k2= [n/5] + [n/25] + [n/125] + [n/625] + ....

where as [x] is greatest integer function
k1= power of 2 in n!

k2= power of 5 in n!

ans=min(k1,k2)

但是我们仍然存在的问题是，我们每次都要计算2和5的幂.如何避免呢? 因为我们必须除以权力.

But problem we still have is we have calculate power of 2 and 5 everytime. how to avoid that ? since we have to divide by power.

1. for 2 , sum=0
2. keep dividing n by 2 (sum+=n/2 and n=n/2)
3. and keep on adding the quotient to sum until n becomes 0.
4. finally sum will give power of 2 in n!

将此重复5次 两者中最小的就是答案.

Repeat this for 5, and minimum among both will be the answer.

工作代码:

// Shashank Jain
#include<iostream>
#include<cstdio>
#define LL long long int
using namespace std;
LL n;
LL power(LL num)
{
        LL sum=0,m,temp;
        m=n;
        while(m>0)
        {
                temp=m/num;
                sum+=temp;
                m/=num;
        }
        return sum;
}
int main()
{
        int t;
        LL k1,k2,ans;
        scanf("%d",&t);
        while(t--)
        {
                scanf("%lld",&n);
                k1=power(2);
                k2=power(5);
                ans=min(k1,k2);
                printf("%lld\n",ans);   
        }
        return 0;
}
// Voila

运行代码链接: Idone代码链接

我刚刚提交了0.54秒和2.6 MB的AC

I just submitted AC with 0.54 sec and 2.6 MB

这篇关于spoj阶乘(超过时间限制错误).我该如何改善我的解决方案?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！