水题入门：关于大数阶乘

最近很无聊啦，去hdu随便翻翻，做一些题来解闷。

看到1042题目，就是求大数阶乘，话说，大数的题目我还没有认真写过！

为什么？我看到大数就会用java写了~（觉得自己好颓废，总是取现成的东西……）

题目就是很简单啦，求0到10000的阶乘

首先，我很快速地用c++写了一下代码，觉得没问题，就是计算10000!阶乘觉得很慢。觉得肯定会tle。但是再认真一看竟然时间限制是5000MS真是很完美。之后我就很高兴地交了上去，后来发现。RuntimerError.不够内存啊！！！！

我第一次用指针int * fact以及malloc啊，我能说我一直都用vector等吗？

竟然出错了……后来我发现我没有free(fact),后来就加上去，还是出错了。还没想明白。

突然，一贯将题目简单化的我，又开始用java写了，话说我好久没写java了，小小生疏。

果断用BigInteger水过了。贴个毫无营养的代码。话说，刷英雄会刷了一段时间，我连hdu要提交的类名是Main都忘记了.

import java.math.*;
import java.util.Scanner;

public class Main {
    public static void main(String [] args){
        int n;
        Scanner sc=new Scanner(System.in);
        while(sc.hasNextInt()){
                n=sc.nextInt();

                BigInteger i=BigInteger.valueOf(n);
                 if(n==0) i=BigInteger.ONE;
                for(int tmp=n-1;tmp>=2;tmp--){
                        i=i.multiply(BigInteger.valueOf(tmp));
                }
                System.out.println(i);
        }


    }
}

不过我没有那么容易放弃c++，水完了之后我马上就去修改我的C++代码了，我放弃了指针数组了，直接申请了int fact[80000]。

提交，轻松过了，不过，运行时间比java长……

突然想起一个很简短的老笑话。

"咚咚咚！"
"谁？"
过了很久。
“java。”

好啦，回归正题，关于大数阶乘，我相信很多人都知道啦（除非你跟我一样水），但是我想用自己的语言来概括一下思路。

1.用数组来记载数字。

2.避免溢出，用高位去乘低位，即像求13阶乘。求到12!=479001600后，

不要这样：? ? ? ? ? ? ?479001600 ? ? ? ? ? ? ? ? ? ? ? ?应该要 ? ? ? ? ? ? ? ? ? ? ? ? ? 13? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

? ? ? ? ? ? ? ? ? ? ? ? ? ? ?X ? ? ? ? ? ? ? ? 13 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? X ? ? 479001600

? ? ? ? ? ? ? ? ? ? ? ? ? ? ?-------------------- ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ------------------------

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?1437004800 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? .

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?479001600 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? .

? ? ? ? ? ? ? ? ? ? ? ? ? ?------------------------ ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? .

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 6227020800 ? ? ? ? ? ? ? ? ? ??

因为这样利用原来的自带的乘法，乘完之后就不会怕溢出，最多就是n+1位。

3.结果直接保存在单元中，再进行进位。

附上C++代码，注释那些是我错误的痕迹，求指正。

/*******************************************************************************/
/* OS           : 3.2.0-58-generic #88-Ubuntu SMP Tue Dec 3 UTC 2013 GNU/Linux
 * Compiler     : g++ (GCC)  4.6.3 (Ubuntu/Linaro 4.6.3-1ubuntu5)
 * Encoding     : UTF8
 * Date         :
 * All Rights Reserved by yaolong.
 *****************************************************************************/
/* Description: ***************************************************************
 *****************************************************************************/
/* Analysis: ******************************************************************
 *****************************************************************************/
/*****************************************************************************/
//*

#include <iostream>
#include <cstdlib>
#include <cmath>
#include <cstring>
using namespace std;
int fact[800000];
class Factorial{
public:
   static void carry(int bit[],int pos){
       int i,carray=0;

       for(i=0;i<=pos;i++){
           bit[i]+=carray;
           if(bit[i]<=9)
              carray=0;
           else if(bit[i]>9&&i<pos){
             carray=bit[i]/10;
             bit[i]=bit[i]%10;

           }else if(bit[i]>9&& i>=pos){

               while(bit[i]>9){
                  carray=bit[i]/10;
                  bit[i]=bit[i]%10;
                  i++;
                  bit[i]=carray;

               }
           }

       }


   }
   static void fac(int n){
      //  int *fact;
     int i,j,digit,pos;
     double sum=0;

     for(i=1;i<=n;i++)
        sum+=log10(i);

     digit=(int)sum+1;          //数据长度
   //  fact=(int *)malloc((digit+1)*sizeof(int));

     memset(fact,sizeof(fact) );   // 初始化数组

     fact[0]=1;                      // 设个位为1

     for(i=2;i<=n;i++){
        for(j=digit;j>=0;j--)
            if(fact[j]!=0){
               pos=j;               //记录最高位
               break;
            }
        for(j=0;j<=pos;j++)
            fact[j]*=i;
        carry(fact,pos);
     }
     for(j=digit;j>=0;j--){            //进位后的最高位
        if(fact[j]!=0){
               pos=j;
                 break;
        }
     }


     for(i=pos;i>=0;i--){

          cout<<fact[i];
     }
   //  free(fact);


   }

};
int main()

{
    int n;
    while(cin>>n){
       Factorial::fac(n);
       cout<<endl;

    }



    return 0;

}