本帖最后由 xutopia 于 2014-12-24 03:00 编辑 |
Assuming the space complexity asked is O(N) word complexity (i.e. O(N) 32-bit integers or something), and arithmetic of words is O(1) time.
1. Precompute everything, hardcode them in a table, do a table look up. O(1) time, if 100,000,000 fits in one word this is O(N) space.
2. Use linked list to implement large number multiplication in a big enough base, say base N. As N!<N^N, which in base-N representation only needs N numbers, so space complexity is O(N) words. Computing N! is O(N^2) time (actually no, see edit note below), once you have N! in base-N, computing the digits in base-10 should be easy.
Edit: In the 2nd approach computing N! in base N should be O(N^2 log N) using FFT, not sure how to get it down to O(N^2) for now, maybe do (N / log N) based arithmetic instead.