HackerRank Extra long factorials

传送门

今天在HackerRank上翻到一道高精度题，于是乎就写了个高精度的模板，说是模板其实就只有乘法而已。

Extra long factorials

Authored by vatsalchanana on Jun 16 2015

Problem Statement

You are given an integer N. Print the factorial of this number.

N!=N×(N−1)×(N−2)×⋯×3×2×1

Note: Factorials of N>20 can't be stored even in a 64−bit long long variable. Big integers must be used for such calculations. Languages like Java, Python, Ruby etc. can handle big integers but we need to write additional code in C/C++ to handle such large values.

We recommend solving this challenge using BigIntegers.

Input Format 
Input consists of a single integer N.

Constraints 
1≤N≤100

Output Format 
Output the factorial of N.

Sample Input

25

Sample Output

15511210043330985984000000
-------------------------------------------------------------------------------------
从前看C++ Primer时，看到Constructor处发现有很多方便的feature，但一般也不写Class，大多忘却了。这回用了一下，还不错。

const int N();

int tmp[N];

struct BigInt{

    int d[N], len;

    BigInt(int n){

        len=!n;

        for(int tmp=n; tmp; len++, tmp/=);

        for(int i=len-; i>=; i--)

            d[i]=n%, n/=;

    }

    BigInt(){}

    void multi(const BigInt &n){

        memset(tmp, , sizeof(tmp));

        for(int i=; i<len; i++)

            for(int j=; j<n.len; j++)

                tmp[i+j]+=d[i]*n.d[j];

        for(int i=len+n.len-; i; i--)

            tmp[i-]+=tmp[i]/, tmp[i]%=;

        int _len=len+n.len-;

        *this=BigInt(tmp[]);

        for(int i=; i<=_len; i++)

            d[len++]=tmp[i];

    }

    void print(){

        for(int i=; i<len; i++)

            printf("%d", d[i]);

        puts("");

    }

};

注意到这里写了两个Constructor，一个带参数的BigInt(int n)以及一个不带参数的BigInt()。如果一个class里没写constructor的话其实还是带有一个default constructor的，这里就是BigInt::BigInt(),但如果定义了Constructor的话default constructor就会被覆盖，所以这里还要将BigInt()显式（explicitly）定义一下，否则 BigInt a；这种声明变量的方式就会报错。

和constructor有关的概念还有type conversion。我们定义了BigInt::BigInt(int n)后求阶乘就可很简洁地写成

    BigInt res();

    for(int i=; i<=n; i++){

        res.multi(i);

    }

我们将int型的变量i传递给函数BigInt::void multi(const BigInt &n)时，int将会自动转换成BigInt，之所以可以这样正是由于我们定义了constructor BigInt(int n) 。