hdu1042N!

http://acm.hdu.edu.cn/showproblem.php?pid=1042

集训第一天比赛上有这个题以前做过一个求150的效率比较低用在这个上面就超时然后在刘汝佳书上看到一种方法勉强可以过 3400+ms

View Code

 1 #include<stdio.h>
 2 #include<string.h>
 3 int x[40000];
 4 int main()
 5 {
 6     int i, n,g,s,d;
 7     while(scanf("%d", &n)!=EOF)
 8     {    
 9         int max = 40000;
10         memset(x,0,sizeof(x));    
11         x[1] =1;
12         d = 0;
13         for(i = 1 ; i <= n ; i++)
14         {
15             for(g= 1 ; g <max ; g++)
16             {
17                 s = x[g]*i+d;
18                 x[g] = s%10;
19                 d = s/10;
20             }
21         }
22         max--;
23         while(x[max]==0)
24         {
25             max--;
26         }
27         for(i = max ;i >= 1 ; i--)
28             printf("%d", x[i]);
29         puts("");
30     }
31     return 0;
32 }

在discuss看到一种做法逢10W进1 234ms 快了不止10倍。。。

View Code

 1 #include<stdio.h>
 2 #include<string.h>
 3 int x[10000];
 4 int main()
 5 {
 6     int i, j, n, m,g,s,d;

 7     while(scanf("%d", &n)!=EOF)
 8     {    
 9         int max = 1;
10         memset(x,0,sizeof(x));    
11         x[1] =1;
12         for(i = 1 ; i <= n ; i++)
13         {
14             for(g= 1 ; g <=max ; g++)
15                 x[g] = x[g]*i;
16             for(g=1 ; g <=max ; g++)
17             {        
18                 d = x[g]/100000;
19                 x[g] = x[g]%100000;
20                 x[g+1] += d;
21             }
22             if(d>0)
23                 max++;
24         }
25         printf("%d", x[max]);
26         for(i = max-1 ;i >= 1 ; i--)
27             printf("%05d", x[i]);
28         puts("");
29     }
30     return 0;
31 }