利用大數乘法的方式算出每一個階層的答案,並將算出來的答案事先先存起來即可。
C++(0.015)
/*******************************************************/ /* UVa 324 Factorial Frequencies */ /* Author: LanyiKnight [at] knightzone.studio */ /* Version: 2015/05/04 */ /*******************************************************/ #include <iostream> #include <cstdio> using namespace std; const int MAXDIGIT = 785; const int MAXNUMBER = 368; int main(){ int num[MAXDIGIT] = {1}, mem[MAXNUMBER][10] = {0}; mem[0][0] = 1; mem[1][1] = 1; for( int i = 2 ; i < MAXNUMBER ; ++i ){ int carry = 0; for( int j = 0 ; j < MAXDIGIT ; ++j ){ num[j] *= i; num[j] += carry; carry = num[j] / 10; num[j] %= 10; } int upperBound; for( upperBound = MAXDIGIT-1 ; upperBound > 0 && num[upperBound] == 0 ; --upperBound ); for( int j = upperBound ; j >= 0 ; --j ){ ++mem[i][num[j]]; } } int n; while( scanf("%d", &n) != EOF && n != 0 ){ printf("%d! --\n", n); for( int i = 0 ; i < 10 ; ++i ){ if( i == 5 ) printf("\n"); if( i % 5 == 0 ){ printf(" "); } else{ printf(" "); } printf("(%d)%5d", i, mem[n][i]); } printf("\n"); } return 0; }
回應