求解n的階乘的十進制表示的最右非零位上的數字[轉]

下面是算法說明

如果用 C 表示 [n/5] + [n/25] + [n/125] + ..., 那麼需要求的是下面的同餘方程

         n ! ≡ x * 10^c (mod 10^(c+1))

的解 x , 0< x ≤ 9.

上面這個同餘方程等價于下面的方程組

        n! ≡ x * 5^c * 2^c (mod 2^(c+1)), n! ≡ x * 2^c * 5^c (mod 5^(c+1))

當 n > 1 時所有的偶數都是上面的方程組中第一個方程的解,而且, n > 1 時該方程組的

第一個方程沒有奇數解,是以 n > 1 時隻需要考慮下面這個方程(即方程組的第二個方程)

的符合 0 < x <9 的偶數解:

         n! ≡ x * 2^c * 5^c (mod 5^(c+1)).                         (a)

用 h(n) 表示 所有與 5 互素且不大于 n 的正整數的連乘積, 則 n! 可以表為

h(n) * 5^[n/5] * h([n/5]) * 5^[n/25] * h([n/25]) * 5^[n/125] * h([n/125]) *... ,

代入 (a) 式,消去 5 的乘方後得到下面的同餘方程

         h(n) * h([n/5]) * h([n/25]) * ... ≡ x * 2^c (mod 5), (b)

由于 3 * 2 ≡ 1 (mod5), 是以 (b) 式變為

         3^c * h(n) * h([n/5]) * h([n/25]) * ...≡ x (mod5),         (c)

由 Euler-Fermat 公式知( % 表示求模運算 )

         3^c ≡ 3 ^ (c % 4) (mod 5),

由 Wilson 定理有

         h(n) ≡ (-1)^([n/5]) * (( n % 5 )! ) (mod 5),

把上面兩式代入 (c) 就得到了

         3^(c%4) * (-1)^c * ( n % 5 )! * ([n/5] % 5)! * ([n/25] % 5)!*...

≡ x (mod 5)                                                  (d)

由 c 的表達式可知, 我們可以在求 [n/5],[n/25],[n/125],... 的過程中

求出 c 和 (n % 5)!,([n/5] % 5)!,([n/25] % 5)!,..., 這樣就可以求得

(d) 式的左邊.把最後的結果 模 5 後即可以求得 x.

這個過程實際上是用連除法求 n 的 5 進制表示. 由于 5 進制表示的 各個 位上的數字是任意的,是以 (d) 式的左邊已不能再簡化.由于任意 求進制表示的 方法本質上都是連除法,是以這個算法 本質上 已是最優算法..

這是一個時間複雜度 O(log n) 的算法