阶乘
N的阶乘定义为：N!=N×(N－1)×……×2×1
请编写一个程序，输出N的阶乘的十进制表示中从最末一个非0位开始自低位向高位数的第M位。
其中：0<=N<=10000，1<=K<=5
例如：N=5,M=2,结果是1（5!=120） N=8,M=3,结果为0（8!=40320）
输入：
第一行一个整数M (1<=M<=100)，代表测试数据的个数；
接下来M行，每行两个整数N，K
输出：
输出M行，每行一个整数，即测试数据的结果。
样例：
输入：
2
5 28 3 输出：
1
0 题意：很明了，就是求n!十进制表示中的从最末一个非0位开始自低位向高位数的第M位。有种思路就是将n!求出来，直接计算。
这种方法耗时828ms，memory 692K。
#include < iostream > #include < string .h > #include < stdio.h > #define MOD 10000 using namespace std; int main( void ) { int t; scanf( " %d " , & t); while (t -- ) { int i,j; int n,k; int digit,carry; //digit表示当前计算的值的位数，carry表示进位 int f[ 10000 ]; char s1[ 50000 ] = { ' \0 ' }; char s2[ 5 ]; long long temp; f[ 0 ] = 1 ; digit = 1 ; scanf( " %d%d " , & n, & k); for (i = 2 ;i <= n;i ++ ) //求n! { carry = 0 ; for (j = 0 ;j < digit;j ++ ) { temp = ( long long )(f[j]) * ( long long )(i) + carry; //此处要用64位数据，防止数据溢出 f[j] = temp % MOD; carry = temp / MOD; } while (carry) { f[digit ++ ] = carry % MOD; carry = carry / MOD; } } i = digit - 1 ; while (f[i] == 0 ) { i -- ; } sprintf(s2, " %d " ,f[i]); strcat(s1,s2); i -- ; for (;i >= 0 ;i -- ) //将结果存进字符数组中以便于处理 { sprintf(s2, " %04d " ,f[i]); //不足4位前面补0 strcat(s1,s2); } for (i = strlen(s1) - 1 ;i >= 0 ;i -- ) { if (s1[i] != ' 0 ' ) break ; } printf( " %d\n " ,s1[i - k + 1 ] - 48 ); } return 0 ; } 下面是另外一种思路
由于是求最末一个非0位开始自低位向高位数的第M位，那么末尾的0则可以忽略掉，并且最多只需保存5位结果即可(M<=5)。
如：n!=A1A2A3..........Ai000000000 Ai!=0
则只需取A(i+4)A(i+3)A(i+2)A(i+1)Ai这5位即可.
耗时0ms，memory 580K，明显效率高很多。
#include < iostream > #define MOD 100000 using namespace std; int main( void ) { int t; scanf( " %d " , & t); while (t -- ) { int n,k; int i,ans; ans = 1 ; scanf( " %d %d " , & n, & k); for (i = n;i >= 2 ;i -- ) { ans *= i; while (ans % 10 == 0 ) // 消除末尾的0 { ans /= 10 ; } if (ans >= MOD) // 只需保存末尾5位数字即可 ans %= MOD; } for (i = 1 ;i < k;i ++ ) { ans = ans / 10 ; } ans = ans % 10 ; printf( " %d\n " ,ans); } return 0 ; }