HDU 1042 求N! ---大数乘法

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.

可能很多人看到这道题，就大叫一声“挖。。。好简单哟！”，然后信心满满的敲下以下的代码：

#include <stdio.h>

int main() {
? ? int n;
? ??
? ? while(scanf("%d",&n) != EOF) {
? ? ? ? int sum = 1;
? ? ? ? for(int i=2; i<=n; i++) {
? ? ? ? ? ? sum *= i;
? ? ? ? }
? ? ? ? printf("%dn",sum);
? ? }
}

然后非常成功的发现--Wrong Answer! 为什么呢？这是因为出现了数据溢出了，不信的话，你可以输入100试一试，为什么会输出0或者是负数，这是数据溢出的一个典例，当n==100时，100!非常大，已经超出了int的表示范围，当然也超过了unsigned long long 的表示范围了，所以对于这种情况，我们就只能用大数乘法来解决了；

解析代码如下：

#include <iostream> #include <cstdio> #include <cstring> #define M 10000 using namespace std; int p[M]; void init() {
    memset(p, 0, sizeof(p));
    p[0] = p[1] = 1; } void multy( int *a,int k) { //乘法函数//////////////////  int carry = 0, tmp; //carry:乘法的进位数  for(int i=1; i<=a[0]+1; i++) {
        tmp = a[i]*k + carry;//开始时由于经验主义错误，误将乘法问题处理成加法问题（ tmp=（a[i]+carry)*k）         a[i] = tmp%10000;
        carry = tmp/10000; } if(a[a[0]+1] != 0)
        a[0]++; } int main() { int n, first; while(cin>>n) {
        init(); for(int i=2; i<=n; i++) {
            multy(p, i); }
        first = 1; for(int i=p[0]; i>=1; i--) { if(first) { //小问题，整型数组最后一位不超过四位时应忽略前导0;                 cout<<p[i];
                first = 0; continue; }
            printf("%04d", p[i]); //输出关键，当后面的整型数组中小于四位时要输出前导0 ""%04d""是关键  }
        cout<<endl; } return 0; }