大数据阶乘（The factorial of large data）

题目描述 Description

阶乘是计算中的基础运算，虽然规则简单，但是位数太多了，也难免会出错。现在的问题是：给定任意位数（long long类型）的一个数，求它的阶乘，请给出正确结果。为提高速度，保证给定运算的结果均为正整数。

输入输出格式 Input/output

输入格式：
一行:一个long long类型的数
输出格式：
一个正整数，表示计算的结果（不可以有前导0）

输入输出样例 Sample input/output

样例测试点#1

输入样例#1：

输出样例#1：

输入样例#2：

输出样例#2：

思路：这题的数据量很大，long long类型的，如果直接计算是不可取的，必须用高精度算法。

这里可以分为几个函数来计算：

①乘法函数：专题里面会细细地讲的

②倒序输出函数：专题里面会细细地讲的

③阶乘函数：要把增序的数转换成数组，再传入乘法函数进行计算

代码如下：

 1 #include <stdio.h>
 2 #include <string.h>
 3 /*=============================================================*/
 4                                   /////////乘法函数////////////// 
 5     
 6 void mul(int a[],int b[])//正整数的高精度运算 a*b ---> c
 7 {
 8     int i=0,j=0,x=0,lenc=0;
 9     int c[99999]; 
10     memset(c,0,sizeof(c));//清零 
11     for(i=1;i<=a[0];i++)
12     {
13         x=0;//表示进位
14         for(j=1;j<=b[0];j++)
15         {
16             c[i+j-1]=c[i+j-1]+a[i]*b[j]+x;
17             x=c[i+j-1]/10;
18             c[i+j-1]=c[i+j-1]%10;
19         }
20         c[i+b[0]]=x;//表示进位(向c的更高位进位)
21     }
22     lenc=a[0]+b[0];
23     while(c[lenc]==0&&lenc>1)  lenc--;
24     c[0]=lenc;
25     for(i=0;i<=lenc;i++)//重新存入数组a 
26     {
27         a[i]=c[i];
28     }
29 }
30 /*==============================================================*/
31                                 /////////倒序输出函数////////////// 
32 void output(int c[])//倒序输出 
33 {
34     int i;
35     for(i=c[0];i>=1;i--)
36     {
37         printf("%d",c[i]);
38     } 
39     printf("
");    
40 }
41 /*==============================================================*/
42                                    /////////计算阶乘函数///////////
43 void kee(long long n)     
44 {    
45     int h,p=0,r=0,q=0;//一堆for用的东西 
46     int i,k=0;//k记录b数组的有多少号元素 
47     int b[99999]={0};//依次增加乘数 
48     int a[99999]={1,1};//当前被乘数 
49     for(i=1;i<=n;i++)
50     {
51         h=1;
52         p=i; 
53         while(p>0)//把阶乘数i转换成数组
54         {
55             b[h]=p%10;
56             p=p/10;
57             k++;
58         }
59         b[0]=k;
60         mul(a,b);//传入乘法函数 
61     }
62     output(a);//输出结果 
63 }
64 /*==============================================================*/
65                                         /////////主函数///////////
66 int main()
67 {    
68     long long n; 
69     scanf("%I64d",&n);
70     if(n==1||n==2)//如果是1、2的话，输出即可 
71     {
72         printf("%I64d
",n);
73     }
74     else if(n<0)
75     {
76         printf("Wrong Answer!
");
77     }
78     else kee(n);//传入阶乘函数 
79     return 0;
80 }