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 コード リンク

AC を 0.54 秒と 2.6 MB で送信しました

于 2013-06-22T20:11:02.007 に答える
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 に答える