f(n) = n! * (n-1)! *...* 2! * 1!
g(n) = f(n) * f(n-1) *... * f(2) * f(1)

求g(n)的位數。

首先，求任何整數 k 的位數，可以透過log求得

=> _└ log₁₀k _┘ + 1   (_{└ ┘}是地板函數 floor)

=> n! 的位數 = _└ log₁₀(n!) _┘ + 1

這裡可以不用將 n! 求出後進行log運算，可以利用高中學過的公式求得 log₁₀n!

令 B = N*M

則 log_aB = log_aNM = log_aN + log_aM

了解了以上公式，則可輕易求出 log₁₀n!

log₁₀(n!) = log₁₀n + log₁₀(n-1) + log₁₀(n-2) ... + log₁₀2 + log₁₀1

-----------------------------------------------------------------------------------------

接著，來整理 f(n) 及 g(n)的部分

g(n) = f(n) * f(n-1) * f(n-2) ... * f(2) * f(1)

             f(n)      =   n! * (n-1)! * (n-2)! ... * 2! * 1!

             f(n-1)   =         (n-1)! * (n-2)! ... * 2! * 1!

             f(n-2)   =                      (n-2)! ... * 2! * 1!

             .

             .

             .

             f(2)    =                                        2! * 1!

X )         f(1)    =                                               1!

-------------------------------------------------------

g(n) = n! * [(n-1)]² * [(n-1)]³ .... * (2!)^n-1 * (1!)ⁿ

所以g(n)的位數

= _└ log₁₀{ n! * [(n-1)]² * [(n-1)]³ .... * (2!)^n-1 * (1!)ⁿ  } _┘ + 1

= _└ log₁₀n! * 2log₁₀(n-1)! * 3log₁₀(n-2)! .... * (n-1)log₁₀(2!) * nlog₁₀(1!)  } _┘ + 1

         n - 1

= _└  Σ [(k+1)log₁₀(n-k)!] _┘ + 1

         k = 0

而這裡的 log₁₀(n-k)! 可以藉由前面的方法求得。

所以在程式一開始，我們可以先將1~10000的階乘log10之後的結果建表

double factorial_log10[10005] = {0}; // n! = factorial_log10[n];
for(int i = 1; i < 10005; i++)
    factorial_log10[i] = factorial_log10[i-1] + log10(i);

然後就可以讀取數字，利用迴圈將階乘log之後的結果乘上(k+1)後累加，得到結果

*部分結果會超出unsigned int儲存範圍，需用long儲存

*累加完之後記得 +1

n! * [(n-1)]² * [(n-1)]³ .... * (2!)^n-1 * (1!)ⁿ

^{更 : [(n-1)!]2 * [(n-1)!]3 才對  少打了!}

感謝分享解題想法

 

所以g(n)的位數

= └ log10{ n! * [(n-1)]2 * [(n-1)]3 .... * (2!)n-1 * (1!)n  } ┘ + 1

= └ log10n! * 2log10(n-1)! * 3log10(n-2)! .... * (n-1)log10(2!) * nlog10(1!)  } ┘ + 1

 

這邊{}拆開應該是變成+，不是*