#UVa:1185-Big Number

對數字取以 10 為底的 log 即可得其位數,故要求 n 階層的位數有多少為:
\(
\begin{align}
GetDigit(n!) & = \lfloor {\log (n!)} \rfloor + 1 \newline
& = \lfloor {\log (n \times (n-1) \times (n-2) \times \dots 1)} \rfloor + 1 \newline
& = \lfloor {\log n} + {\log (n-1)} + {\log (n-2)} + \dots + {\log 1} \rfloor + 1 \newline
\end{align}
\)

透過公式了解可以對各項取 Log 再加總後,就利用 DP 解決即可。

C++(0.330)

/*******************************************************/
/* UVa 1185 Big Number                                 */
/* Author: Maplewing [at] knightzone.org               */
/* Version: 2018/05/17                                 */
/*******************************************************/
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;

int main(){
  int caseCount;
  scanf("%d", &caseCount);

  double logValue[10000005] = {0};
  int maxNumber = 0;
  for(int caseNumber = 0 ; caseNumber < caseCount ; ++caseNumber){
    int n;
    scanf("%d", &n);

    if( n > maxNumber ){
      for(int i = maxNumber + 1 ; i <= n ; ++i ){
        logValue[i] = logValue[i-1] + log10(i);
      }
    }

    printf("%d\n", (int)logValue[n] + 1);
  }

  return 0;
}

沒有迴響

本文還沒有迴響,快來搶頭香!

發表迴響