tju 1011有这么一个问题:
http://acm.tongji.edu.cn/showproblem.php?problem_id=1011

Problem
对于小于25000的自然数n,求阶乘n!,(n-1)!,(n-2)!...3!,2!,1!右边的非零数之和。 

例如： 

当n=5时，
5!=120,右边非零数为2;
4!=24,右边非零数为4;
3!=6,右边非零数为6;
2!=2,右边非零数为2;
1!=1,右边非零数为1。
其右边的非零数之和为15。 

Input
本题有多组数据，每组数据包含一个正整数N(N不大于25000)占一行。 

Output
对给定的每组输入数据，输出一个整数。每个结果占一行。不要输出额外的空行。 

Sample Input
5
10
1

Sample Output
15
39
1

现在问,在N非常大的时候,如何快速计算结果.
比如现在改(N不大于25000)为N不大于100000000000000=10^15,如何计算.
或者对于更加大的N,应该如何计算.
参考答案:
Sample Input:
1000000000000
10000000000000
100000000000000
1000000000000000

Sample Output:
4999999994345
49999999994553
500000000009803
4999999999996345


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


#include <stdio.h>
#include <string.h>
#include <windows.h>

int m_map_head[30][4]; // 每一区的前四个数
unsigned __int64 m_map[30][10]; // m_map[n][i],i=2,4,6,8 指第n区(层)对应i开门的组的阶乘最后非零和
int s_map[30][10][5]; // s_map_[n][i][j],i=2,4,6,8 指第n区i到第n-1区的映射

int get_n( unsigned __int64 n, int last );
int get_first( int level, unsigned __int64 &pos );
int get_next( int level, int value, unsigned __int64 current, unsigned __int64 &pos  );
void get_s_map( int level, int m[30][10][5] );

unsigned __int64 pow( int a, int n )
{
unsigned __int64 result = 1;
for( int i = 0; i < n; ++i )
result *= a;
return result;
}

/*
 * 初始化 m_map_head, m_map, s_map,方法看分析,用文字不好说
 */
void init()
{
int i,j,k;
for( i = 0; i < 24; ++i )
get_s_map(i,s_map);

memset( m_map, 0, 30*10*sizeof(__int64));
for( i = 0; i < 10; ++i )
m_map[0][i] = i;
for( j = 1; j < 30; ++j ){
for( i = 0; i < 10; ++i ){
for( k = 0; k < 5; ++k )
m_map[j][i] += m_map[j-1][s_map[j][i][k]];
}
}
}

/*
 * 得到 n! 最后一位非零
 * last: (n-1)!的最后一位非零
 * 根据 (n-1)!中有足够的 2 让 n 中的 5 合成 10
 */
int get_n( unsigned __int64 n, int last )
{
int Map[10]  = { 0, 0, 6, 0, 2, 0, 8, 0, 4, 0 };
while( !(n%5) ){
n /= 5;
last = Map[last];
}
return (int)(n*last%10);
}

/*
 * 得到第level区(层)的第一个数
 * pos: out, 给出这第一个数在第0区的映射位置
 */
int get_first( int level, unsigned __int64 &pos)
{
int tmp;
if( level == 0 ){
pos = 1;
return 1;
}
else{
// 因为level层的第一个是level-1层的第5个数开始
tmp = get_first( level-1,pos );
tmp = get_next( level-1, tmp,pos,pos);
tmp = get_next( level-1, tmp,pos,pos);
tmp = get_next( level-1, tmp,pos,pos);
tmp = get_next( level-1, tmp,pos,pos);
return tmp;
}
}


int get_next( int level,int value, unsigned __int64 current, unsigned __int64 &pos )
{
int last = value;
pos = current + pow(5,level);
while( level > 0 ){
last = s_map[level][last][4];
--level;
}
last = get_n( pos, last);
return last;
}

/*
 * 是否已经得到了2,4,6,8映射到下一层需要的数据量
 * got[i] 说明i已经足够
 */
bool enough( bool got[10] )
{
return got[2] && got[4] && got[6] && got[8];
}

/*
 * 得到 level到level-1层的映射数据
 */
void get_s_map( int level, int m[30][10][5] )
{
if( level == 0 ){
memset( m, 0, 10*5*sizeof(int));
m[level][2][0] = 2,m[level][4][0] = 4,m[level][6][0] = 6,m[level][8][0] = 8;
return;
}
else{
int _serial[640],_cur = 1,node = 0;
bool got[10] = {false};
unsigned __int64 pos;
_serial[_cur] = get_first( level-1, pos);
++_cur;
while( !enough(got) ){
_serial[_cur] = get_next(level-1,_serial[_cur-1], pos, pos);
if( 5 == node ){
got[_serial[_cur]] = true;
node = 0;
}
++_cur;
++node;
}
_serial[_cur] = get_next(level-1,_serial[_cur-1], pos, pos);
++_cur;
_serial[_cur] = get_next(level-1,_serial[_cur-1], pos, pos);
++_cur;
_serial[_cur] = get_next(level-1,_serial[_cur-1], pos, pos);
++_cur;
_serial[_cur] = get_next(level-1,_serial[_cur-1], pos, pos);
++_cur;
m_map_head[level-1][0] = _serial[1];
m_map_head[level-1][1] = _serial[2];
m_map_head[level-1][2] = _serial[3];
m_map_head[level-1][3] = _serial[4];
for( int i = 5; i < _cur; i += 5 ){
if( got[_serial[i]] ){
m[level][_s