USACO 3.2 Factorials(高精度乗算)

水が通るでしょう.O(n^2)のアルゴリズムを直接シミュレートし,O(n*logn)のアルゴリズムがあり,研究した.
浙江大学はNを求めます!最後に0ビット以外の階乗テンプレート.2012.11.22

#include <cstdio>

#include <cstring>

#include <string>

#include <cmath>

#include <queue>

using namespace std;

int lastdigit(char* buf)

{

    const int mod[20] = {1,1,2,6,4,2,2,4,2,8,4,4,8,4,6,8,8,6,8,2};

    int len = strlen(buf),a[10000],i,c,ret = 1;

    if(len == 1)

    return mod[buf[0]-'0'];

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

    {

        a[i] = buf[len-1-i]-'0';

    }

    for(;len;len-=!a[len-1])

    {

        ret = ret*mod[a[1]%2*10+a[0]]%5;//       。。

        for(c = 0,i = len-1;i >= 0;i --)

        {

            c = c*10+a[i],a[i]=c/5,c%=5;

        }

    }

    return ret+ret%2*5;

}

int main()

{

    char str[501];

    while(scanf("%s",str)!=EOF)

    {

        printf("%d
",lastdigit(str));

    }

    return 0;

}

 

 1 /*

 2    ID: cuizhe

 3    LANG: C++

 4    TASK: fact4

 5 */

 6 #include<stdio.h>

 7 #include<string.h>

 8 int p[300000];

 9 int main()

10 {

11     int a,b,i,j;

12     freopen("fact4.in","r",stdin);

13     freopen("fact4.out","w",stdout);

14     scanf("%d",&a);

15     p[0]=1;

16     j=0;

17     for(b=1; b<=a; b++)

18     {

19         for(i=0; i<=j; i++)

20         {

21             p[i]=p[i]*b;

22         }

23         for(i=0; i<=j; i++)

24         {

25             if(p[i]>9)

26             {

27                 p[i+1]+=p[i]/10;

28                 p[i]=p[i]%10;

29                 if(i+1>j)

30                     j=i+1;

31             }

32         }

33     }

34     for(i = 0; i <= j; i++)

35     {

36         if(p[i] != 0)

37         {

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

39             break;

40         }

41     }

42     return 0;

43 }