hdu1042 - N！

约定不等于承诺〃 2022-07-13 04:57 11阅读 0赞

# 地址 #

[http://acm.hdu.edu.cn/showproblem.php?pid=1042][http_acm.hdu.edu.cn_showproblem.php_pid_1042]

# 定位 #

*  大数乘法问题
 *  万进制

# 分析 #

*  分析题设的资源限制条件，确定本题的主要问题是`n！`结果过大引发的存储问题，即大数乘法问题。
    
    根据Stirling公式，n！≈2πn−−−√(ne)n，计算`n！`的时间复杂度很大。题设中，给定的时间限制为罕见的10000ms，命题者显然并不是在时间复杂度上设置难点，结题策略上朴素计算即可。
    
    与此同时，由结果过大引发的存储问题更加突出。`unsigned long long`类型能存储19位整数，然而，21！就已经达到了19位数。因此，本题归类为大数问题。
 *  数组中每个元素存储一位大数的存储策略仍然是不够的，空间上不够(开辟的数组过大)，时间上也不够(处理进位的时间过长)。因此，采用万进制的存储策略，即数组中每个元素存储多位大数(这里采用10000)。

# 代码 #

#include <stdio.h>
    #include <stdlib.h>
    #define RULE 10000
    
    int main()
    {
        int n,i,j;
        int c;
        int tmp;
        int LEN;
        int result[10000];
        while(scanf("%d",&n) != EOF)
        {
            memset(result,0,sizeof(result));
            result[0] = 1;
            LEN = 1;
            for(i=2;i<=n;i++)
            {
                c = 0;
                for(j=0;j<LEN;j++)
                {
                    tmp = result[j]*i + c;
                    result[j] = tmp%RULE;
                    c = tmp/RULE;
                }
                while(c)
                {
                    result[LEN] = c%RULE;
                    c = c/RULE;
                    LEN++;
                }
            }
            printf("%d",result[LEN-1]);
            for(i=LEN-1;i>0;i--)
            {
                printf("%04d",result[i-1]);
            }
            printf("\n");
        }
        return 0;
    }

# 性能 #

<table> 
 <thead> 
  <tr> 
   <th align="center">Exe.Time</th> 
   <th align="center">Exe.Memory</th> 
   <th align="center">Code Length</th> 
   <th align="center">Language</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="center">0MS</td> 
   <td align="center">1732K</td> 
   <td align="center">934B</td> 
   <td align="center">c</td> 
  </tr> 
 </tbody> 
</table>

# 总结 #

## c语言标准输入输出库函数 ##

*  scanf()
    
     *  %c，读取任何字符，包括空格和换行符。
     *  %s，检测到空格和换行符停止读取，空格和换行符不会被丢弃。
     *  数值，读取到数值之前遇到空格和换行符，自动丢弃，继续读取；读取数值过程中，检测到空格和换行符停止读取，空格和换行符不会被丢弃。
 *  gets()
    
     *  读取一行，包括空格，检测到换行符停止读取，换行符被丢弃。
     *  以`\0`标志字符串结尾。
 *  getchar()
    
     *  读取一个任意字符，常用于`scanf()`后清除多余的空格或换行符。

## 格式审题 ##

*  输入
    
    根据题目提示，第一行末尾的换行符需要进行丢弃处理，其余各行采用`gets()`读入，自动处理了行尾换行符。
 *  输出
    
    行内，检测到空格进行一次反转操作，反转字符串后，输出空格。
    
    行尾，检测到`\0`进行一次反转操作，反转字符串后，输出换行符。

> 经试验，最后一行结果输出后，也应输出换行符。因此，不必对最后一行特殊处理。

Thanks everyone

[http_acm.hdu.edu.cn_showproblem.php_pid_1042]: http://acm.hdu.edu.cn/showproblem.php?pid=1042