SPOJ階乘問題

Question

我試圖開發SPOJ階乘問題數11.下面的代碼是我的代碼

import java.math.*; 
import java.io.*; 
public class Problem11 { 

/** 
* Count the number of zeroes at the end of 
* the factorial value of a number. 
*/ 
public static void main(String[] args) throws IOException 
{ 
BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 
int numOfInputs=0; 
numOfInputs=Integer.parseInt(br.readLine()); 
BigInteger nextNum[]=new BigInteger[numOfInputs]; 
BigInteger factValue[]=new BigInteger[numOfInputs]; 

//Get all the numbers to be computed 
for(int count=0;count<numOfInputs;count++) 
{ 
    nextNum[count]=new BigInteger(br.readLine()); 
} 

//Obtain the factorial value for each number 
for(int count=0;count<numOfInputs;count++) 
{ 
    factValue[count]=getFact(nextNum[count]); 
} 

//Obtain the number of trailing zeroes 
for(int count=0;count<numOfInputs;count++) 
{ 
    //System.out.println(factValue[count]); 
    System.out.println(getZeroes(factValue[count])); 

} 
} 


public static String getZeroes(BigInteger num) 
{ 
    int numOfZeroes=0; 
    while(num.remainder(BigInteger.TEN).equals(BigInteger.ZERO)) 
    { 
     num=num.divide(BigInteger.TEN); 
     numOfZeroes++; 
    } 
    return String.valueOf(numOfZeroes); 
} 



public static BigInteger getFact(BigInteger num) 
{ 
    BigInteger factorial=BigInteger.ONE;  
    if(num.equals(0)) 
    { 
     return (BigInteger.valueOf(1)); 
    } 
    else 
    { 
     int count=1; 
     while((BigInteger.valueOf(count).compareTo(num))<=0)   
     {    
      factorial=factorial.multiply(BigInteger.valueOf(count)); 
      count++; 
     } 
    } 

    return factorial; 

} 

} 

代碼工作罰款數達5位數字以小的延遲，並在過去的數 8735373它花費了太多時間，如果我提交我的解決方案，法官顯示編譯錯誤..我無法弄清楚錯誤是什麼。請看看我的代碼，並幫助我找出問題所在。

Answer 1

您可以查看此方法來查找the number of trailing zeros in n!。

import java.util.*; 

public class Main { 

    public static void main(String[] args) { 
     Scanner in = new Scanner(System.in); 
     int count = in.nextInt(); 
     for (int i = 0; i < count; i++) { 
      int n = in.nextInt(); 
      int result = 0; 
      for (int d = 5; d <= n; d *= 5) { 
       result += n/d; 
      } 
      System.out.println(result); 
     } 
    } 
} 

Answer 2

你的方法（幼稚：計算實際階乘值，然後手動計算零）不會通過，無論如何。看看極端情況（即階乘的上限，我甚至不認爲給定的內存限制足以計算它）。從不同的角度看問題，思考真正的問題是什麼，這是問題解決的藝術;）

提示：什麼可以產生和添加更多0到一個數字的末尾，特別是乘法？

Answer 3

原因你的錯誤是應該public class Main

而且您的代碼就會TLE，則必須觀察蠻力將永遠不會在SPOJ工作。解決這個問題的方法是看到一個有趣的模式，權力爲5，最後爲零。

Answer 4

這裏是C中的一個解決方案。我們不需要計算這個問題的確切因子。

#include <stdio.h> 
#include <stdlib.h> 
#include <math.h> 
#define MAX 1000000 
int xpn(int x, int n){ 
int prod=1; 
while(n){ 
prod*=x; 
n--; 
} 
return prod; 
} 
int trail(int x){ 
int numZero=0; 
int i=1; 
int k; 
for(;x/xpn(5,i);i++){ 
numZero+=(x/xpn(5,i)); 
} 
return numZero; 
} 
int main(int argc, char **argv){ 
#if 1 
int n; 
int num[MAX]; 
int zero[MAX]; 
scanf("%d",&n); 
int count=n; 
int i=0; 
while(count){ 
scanf("%d",&num[i]); 
zero[i]=trail(num[i]); 
printf("%d\n",zero[i]); 
i++; 
count--; 
} 
#endif 
return 0; 
}