spoj factorial(超出时间限制错误).我该如何改进我的解决方案？

Question

这是我关于spoj的问题的链接.

我已尝试使用递归和非递归.但是我的时间限制超出了错误.我该如何改进我的解决方案？

我已经展示了以下两种解决方案.

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));

}

Answer 1

问题减少到n中找到10的力量!(n的阶乘),但为此我们必须找到2和5的幂,因为10个因素分解为2和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的功率.怎么避免呢？因为我们必须按权力划分.

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次,两者之间的最小值将是答案.

工作守则:

// 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

运行代码链接:Ideone代码链接

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