首先我们先求n!位数
可以将n!表示成10的次幂,即n!=10^M(10的M次方)则不小于M的最小整数就是 n!的位数，对该式两边取对数，有 M =log10^n!
即：
M = log10^1+log10^2+log10^3…+log10^n
循环求和,就能算得M值，该M是n!的精确位数。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
#include<iostream> #include<cmath> using namespace std; int main() { int n; int i; double d; while (cin>>n) { d=0; for (i=1;i<=n;i++) { d+=(double)log10(i); } cout<<(int)d+1<<endl; } return 0; } |
接下来，求n!的具体值
具体题目原型来自HDOJ ：http://acm.hdu.edu.cn/showproblem.php?pid=1042
C++ Version:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 |
#include <iostream> #include <cstring> /* 一个数组元素表示 4 个十进制位，即数组是万进制的 */ #define BIG_RADIX 10000 #define RADIX_LEN 4 /* 10000! 有 35660 位 */ #define MAX_LEN (35660/RADIX_LEN + 1) using namespace std; int x[MAX_LEN + 1]; void Big_Print() { int start_output = 0;//用于跳过多余的0 for (int i=MAX_LEN;i>= 0;--i) { if (start_output == 1){//如果多余的0已经跳过，则输出 cout<<x[i]; } else if (x[i] > 0){//表示多余的0已经跳过 cout<<x[i]; start_output = 1; } } if (start_output == 0)//如果全为0 cout<<"0"; } void Big_Multiple(int y) { int carry = 0;//保存进位 int tmp; for (int i=0;i<MAX_LEN;++i) { tmp = x[i] * y + carry; x[i] = tmp % BIG_RADIX; carry = tmp / BIG_RADIX; } } void Big_Factorial(int N) { memset(x, 0, sizeof(x)); x[0] = 1; for (int i=2; i<=N;++i){ Big_Multiple(i); } } int main(void) { int N; while (cin>>N) { Big_Factorial(N); Big_Print(); cout<<endl; } return 0; } |
C Version:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 |
#include <stdio.h> #include <string.h> /* 一个数组元素表示 4 个十进制位，即数组是万进制的 */ #define BIG_RADIX 10000 #define RADIX_LEN 4 /* 10000! 有 35660 位 */ #define MAX_LEN (35660/RADIX_LEN + 1) int x[MAX_LEN + 1]; void Big_Print(){ int i; int start_output = 0;//用于跳过多余的0 for (i = MAX_LEN; i >= 0; --i){ if (start_output == 1){//如果多余的0已经跳过，则输出 printf("%04d", x[i]); } else if (x[i] > 0){//表示多余的0已经跳过 printf("%d", x[i]); start_output = 1; } } if (start_output == 0)//如果全为0 printf("0"); } void Big_Multiple(int y){ int i; int carry = 0;//保存进位 int tmp; for (i = 0; i < MAX_LEN; ++i){ tmp = x[i] * y + carry; x[i] = tmp % BIG_RADIX; carry = tmp / BIG_RADIX; } } void Big_Factorial(int N){ int i; memset(x, 0, sizeof(x)); x[0] = 1; for (i = 2; i <= N; ++i){ Big_Multiple(i); } } int main(void){ int N; while (scanf("%d", &N) != EOF){ Big_Factorial(N); Big_Print(); printf("\n"); } } |
