N! HDU 1042

N!

Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 60244 Accepted Submission(s): 17166

Problem Description

Given an integer N(0 ≤ N ≤ 10000), your task is to calculate N!

Input

One N in one line, process to the end of file.

Output

For each N, output N! in one line.

Sample Input

1 2 3

Sample Output

1 2 6

 1 #include <iostream>
 2 #include<stdio.h>
 3 #include<string.h>
 4 #include<math.h>
 5 #include<stdlib.h>
 6 using namespace std;
 7 int a[8000];
 8 int main()
 9 {
10     int n;
11     int i,j;
12     while(~scanf("%d",&n))
13     {
14         if(n==0)
15         {
16             printf("1
");
17             continue;
18         }
19         memset(a,0,sizeof(a));
20         a[0]=1;
21         for(i=2;i<=n;i++)
22         {
23             for(j=0;j<8000;j++)
24             a[j]*=i;
25             for(j=0;j<8000;j++)
26             {
27                 a[j+1]+=a[j]/100000;
28                 a[j]%=100000;
29             }
30         }
31         for(i=8000;i>=0;i--)
32         {
33             if(a[i]!=0)
34             break;
35         }
36         printf("%d",a[i--]);
37         for(;i>=0;i--)
38         printf("%05d",a[i]);
39         printf("
");
40     }
41     return 0;
42 }
43 -----------------------------------------------
44 #include <iostream>
45 #include<stdio.h>
46 #include<string.h>
47 #include<math.h>
48 #include<stdlib.h>
49 using namespace std;
50 int a[100000];
51 int main()
52 {
53     //freopen("in.txt","r",stdin);
54     int n;
55     int i,j,temp;
56     while(~scanf("%d",&n))
57     {
58         memset(a,0,sizeof(a));
59         a[0]=1;
60         int count=1;
61         for(i=1;i<=n;i++)
62         {
63             int k=0;
64             for(j=0;j<count;j++)
65             {
66                 temp = a[j]*i+k;
67                 a[j]=temp%10;
68                 k=temp/10;
69             }
70             while(k)
71             {
72                 a[count++]=k%10;
73                 k/=10;
74             }
75         }
76         for(i=100000;i>=0;i--)
77         {
78             if(a[i]!=0)
79             break;
80         }
81         for(;i>=0;i--)
82         printf("%d",a[i]);
83         printf("
");
84     }
85     return 0;
86 }

模板：

  1 #include <stdio.h>
  2 #include <string.h>
  3 #include <stdlib.h>
  4 #include <math.h>
  5 #include <assert.h>
  6 #include <ctype.h>
  7 #include <map>
  8 #include <string>
  9 #include <set>
 10 #include <bitset>
 11 #include <utility>
 12 #include <algorithm>
 13 #include <vector>
 14 #include <stack>
 15 #include <queue>
 16 #include <iostream>
 17 #include <fstream>
 18 #include <list>
 19 using  namespace  std;
 20 
 21 const  int MAXL = 100000;
 22 struct  BigNum
 23 {
 24     int  num[MAXL];
 25     int  len;
 26     BigNum()
 27     {
 28         memset(num,0,sizeof(num));
 29     }
 30 };
 31 
 32 //高精度比较 a > b return 1, a == b return 0; a < b return -1;
 33 int  Comp(BigNum &a, BigNum &b)
 34 {
 35     int  i;
 36     if(a.len != b.len) return (a.len > b.len) ? 1 : -1;
 37     for(i = a.len-1; i >= 0; i--)
 38         if(a.num[i] != b.num[i]) return  (a.num[i] > b.num[i]) ? 1 : -1;
 39     return  0;
 40 }
 41 
 42 //高精度加法
 43 BigNum  Add(BigNum &a, BigNum &b)
 44 {
 45     BigNum c;
 46     int  i, len;
 47     len = (a.len > b.len) ? a.len : b.len;
 48     memset(c.num, 0, sizeof(c.num));
 49     for(i = 0; i < len; i++)
 50     {
 51         c.num[i] += (a.num[i]+b.num[i]);
 52         if(c.num[i] >= 10)
 53         {
 54             c.num[i+1]++;
 55             c.num[i] -= 10;
 56         }
 57     }
 58     if(c.num[len])
 59         len++;
 60     c.len = len;
 61     return  c;
 62 }
 63 //高精度乘以低精度，当b很大时可能会发生溢出int范围,具体情况具体分析
 64 //如果b很大可以考虑把b看成高精度
 65 BigNum Mul1(BigNum &a, int  &b)
 66 {
 67     BigNum c;
 68     int  i, len;
 69     len = a.len;
 70     memset(c.num, 0, sizeof(c.num));
 71     //乘以0，直接返回0
 72     if(b == 0)
 73     {
 74         c.len = 1;
 75         return  c;
 76     }
 77     for(i = 0; i < len; i++)
 78     {
 79         c.num[i] += (a.num[i]*b);
 80         if(c.num[i] >= 10)
 81         {
 82             c.num[i+1] = c.num[i]/10;
 83             c.num[i] %= 10;
 84         }
 85     }
 86     while(c.num[len] > 0)
 87     {
 88         c.num[len+1] = c.num[len]/10;
 89         c.num[len++] %= 10;
 90     }
 91     c.len = len;
 92     return  c;
 93 }
 94 
 95 //高精度乘以高精度,注意要及时进位，否则肯能会引起溢出,但这样会增加算法的复杂度，
 96 //如果确定不会发生溢出, 可以将里面的while改成if
 97 BigNum  Mul2(BigNum &a, BigNum &b)
 98 {
 99     int i, j, len = 0;
100     BigNum  c;
101     memset(c.num, 0, sizeof(c.num));
102     for(i = 0; i < a.len; i++)
103     {
104         for(j = 0; j < b.len; j++)
105         {
106             c.num[i+j] += (a.num[i]*b.num[j]);
107             if(c.num[i+j] >= 10)
108             {
109                 c.num[i+j+1] += c.num[i+j]/10;
110                 c.num[i+j] %= 10;
111             }
112         }
113     }
114     len = a.len+b.len-1;
115     while(c.num[len-1] == 0 && len > 1)
116         len--;
117     if(c.num[len])
118         len++;
119     c.len = len;
120     return  c;
121 }
122 void  print(BigNum &a)   //输出大数
123 {
124     int  i;
125     for(i = a.len-1; i >= 0; i--)
126         printf("%d", a.num[i]);
127     puts("");
128 }
129 
130 void Init(BigNum &a, char *s, int &tag)   //将字符串转化为大数
131 {
132     int  i = 0, j = strlen(s);
133     if(s[0] == '-')
134     {
135         j--;
136         i++;
137         tag *= -1;
138     }
139     a.len = j;
140     for(; s[i] != ''; i++, j--)
141         a.num[j-1] = s[i]-'0';
142 }
143 
144 int main(void)
145 {
146     int n;
147     while(~scanf("%d",&n))
148     {
149         BigNum a;
150         int tag=1;
151         Init(a,"1",tag);
152         for(int i=1;i<=n;i++)
153         {
154             a=Mul1(a,i);
155         }
156         print(a);
157     }
158     return 0;
159 }

View Code