1

这是我在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));

}
4

4 回答 4

5

问题减少到这个在 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

于 2013-06-22T20:11:02.007 回答
3

这是一个提示 - n 末尾的零数！由 10 整除 n! 的次数给出。这等于 5 除以 n 的次数的最小值！和 2 除以 n! 的次数。尝试看看您是否可以直接计算这些值而不是尝试计算 n!，因为即使是合理的 n（例如，n = 100），n! 的值也是如此。太大而无法放入 a 中long long，您会得到错误的答案。

希望这可以帮助！

于 2013-06-22T19:27:16.000 回答
2 
//count n! tail zero
//count the number of 5 in the prime factor.
int noz(int n){
    int count;

    if(n < 5) return 0;
    count = n / 5;
    return count + noz(count);
}
于 2013-06-22T19:51:33.103 回答
0

约束是：

1 <= N <= 1000000000

但N!不适合 64 位整数（在计算机内存中也不适合）。由于您无法计算阶乘本身，因此您必须找到其他方法。这个页面给出了一个严肃的提示。

于 2013-06-22T19:25:35.213 回答