Last non-zero Digit in N!

#include <bits/stdc++.h>using namespace std;/** 完全大数模板* 输出cin>>a* 输出a.print();* 注意这个输入不能自动去掉前导0的，可以先读入到char数组，去掉前导0，再用构造函数。*/#define MAXN 9999#define MAXSIZE 1010#define DLEN 4int data[]={1,1,2,6,4,4,4,8,4,6};//0-9的最后一位非零数(去掉5的)int TwoMod[]={2,4,8,6};class BigNum {    public:        int a[500];  //可以控制大数的位数        int len;    public:        BigNum()        {            len=1;memset(a,0,sizeof(a));        }  //构造函数        BigNum(const int);     //将一个int类型的变量转化成大数        BigNum(const char*);   //将一个字符串类型的变量转化为大数        BigNum(const BigNum &); //拷贝构造函数        BigNum &operator=(const BigNum &); //重载赋值运算符，大数之间进行赋值运算        friend istream& operator>>(istream&,BigNum&); //重载输入运算符        friend ostream& operator<<(ostream&,BigNum&); //重载输出运算符        BigNum operator+(const BigNum &)const;  //重载加法运算符，两个大数之间的相加运算        BigNum operator-(const BigNum &)const;  //重载减法运算符，两个大数之间的相减运算        BigNum operator*(const BigNum &)const;  //重载乘法运算符，两个大数之间的相乘运算        BigNum operator/(const int &)const;     //重载除法运算符，大数对一个整数进行相除 运算        BigNum operator^(const int &)const;     //大数的n次方运算        int operator%(const int &)const;        //大数对一个int类型的变量进行取模运算        bool operator>(const BigNum &T)const;   //大数和另一个大数的大小比较        bool operator>(const int &t)const;      //大数和一个int类型的变量的大小比较        void print();        //输出大数};BigNum::BigNum(const int b)   //将一个int类型的变量转化为大数{    int c,d=b;    len=0;    memset(a,0,sizeof(a));    while(d>MAXN)    {        c=d-(d/(MAXN+1))*(MAXN+1);        d=d/(MAXN+1);        a[len++]=c;    }    a[len++]=d;}BigNum::BigNum(const char *s)  //将一个字符串类型的变量转化为大数{    int t,k,index,L,i;    memset(a,0,sizeof(a));    L=strlen(s);    len=L/DLEN;    if(L%DLEN)        len++;    index=0;    for(i=L-1;i>=0;i-=DLEN)    {        t=0;        k=i-DLEN+1;        if(k<0)            k=0;        for(int j=k;j<=i;j++)            t=t*10+s[j]-‘0‘;        a[index++]=t;    }}BigNum::BigNum(const BigNum &T):len(T.len)  //拷贝构造函数{    int i;    memset(a,0,sizeof(a));    for(i=0;i<len;i++)        a[i]=T.a[i];}BigNum & BigNum::operator=(const BigNum &n)  //重载赋值运算符，大数之间赋值运算{    int i;    len=n.len;    memset(a,0,sizeof(a));    for(i=0;i<len;i++)        a[i]=n.a[i];    return *this;}istream& operator>>(istream &in,BigNum &b){    char ch[MAXSIZE*4];    int i=-1;    in>>ch;    int L=strlen(ch);    int count=0,sum=0;    for(i=L-1;i>=0;)    {        sum=0;        int t=1;        for(int j=0;j<4&&i>=0;j++,i--,t*=10)        {            sum+=(ch[i]-‘0‘)*t;        }        b.a[count]=sum;        count++;    }    b.len=count++;    return in;}ostream& operator<<(ostream& out,BigNum& b)  //重载输出运算符{    int i;    cout<<b.a[b.len-1];    for(i=b.len-2;i>=0;i--)    {        printf("%04d",b.a[i]);    }    return out;}BigNum BigNum::operator+(const BigNum &T)const   //两个大数之间的相加运算{    BigNum t(*this);    int i,big;    big=T.len>len?T.len:len;    for(i=0;i<big;i++)    {        t.a[i]+=T.a[i];        if(t.a[i]>MAXN)        {            t.a[i+1]++;            t.a[i]-=MAXN+1;        }    }    if(t.a[big]!=0)        t.len=big+1;    else        t.len=big;    return t;}BigNum BigNum::operator-(const BigNum &T)const  //两个大数之间的相减运算{    int i,j,big;    bool flag;    BigNum t1,t2;    if(*this>T)    {        t1=*this;        t2=T;        flag=0;    }    else    {        t1=T;        t2=*this;        flag=1;    }    big=t1.len;    for(i=0;i<big;i++)    {        if(t1.a[i]<t2.a[i])        {            j=i+1;            while(t1.a[j]==0)                j++;            t1.a[j--]--;            while(j>i)                t1.a[j--]+=MAXN;            t1.a[i]+=MAXN+1-t2.a[i];        }        else            t1.a[i]-=t2.a[i];    }    t1.len=big;    while(t1.a[len-1]==0 && t1.len>1)    {        t1.len--;        big--;    }    if(flag)        t1.a[big-1]=0-t1.a[big-1];    return t1;}BigNum BigNum::operator*(const BigNum &T)const  //两个大数之间的相乘{    BigNum ret;    int i,j,up;    int temp,temp1;    for(i=0;i<len;i++)    {        up=0;        for(j=0;j<T.len;j++)        {            temp=a[i]*T.a[j]+ret.a[i+j]+up;            if(temp>MAXN)            {                temp1=temp-temp/(MAXN+1)*(MAXN+1);                up=temp/(MAXN+1);                ret.a[i+j]=temp1;            }            else            {                up=0;                ret.a[i+j]=temp;            }        }        if(up!=0)            ret.a[i+j]=up;    }    ret.len=i+j;    while(ret.a[ret.len-1]==0 && ret.len>1)        ret.len--;    return ret;}BigNum BigNum::operator/(const int &b)const  //大数对一个整数进行相除运算{    BigNum ret;    int i,down=0;    for(i=len-1;i>=0;i--)    {        ret.a[i]=(a[i]+down*(MAXN+1))/b;        down=a[i]+down*(MAXN+1)-ret.a[i]*b;    }    ret.len=len;    while(ret.a[ret.len-1]==0 && ret.len>1)        ret.len--;    return ret;}int BigNum::operator%(const int &b)const   //大数对一个 int类型的变量进行取模{    int i,d=0;    for(i=len-1;i>=0;i--)        d=((d*(MAXN+1))%b+a[i])%b;    return d;}BigNum BigNum::operator^(const int &n)const  //大数的n次方运算{    BigNum t,ret(1);    int i;    if(n<0)exit(-1);    if(n==0)return 1;    if(n==1)return *this;    int m=n;    while(m>1)    {        t=*this;        for(i=1;(i<<1)<=m;i<<=1)            t=t*t;        m-=i;        ret=ret*t;        if(m==1)            ret=ret*(*this);    }    return ret;}bool BigNum::operator>(const BigNum &T)const    //大数和另一个大数的大小比较{    int ln;    if(len>T.len)        return true;    else if(len==T.len)    {        ln=len-1;        while(a[ln]==T.a[ln]&&ln>=0)            ln--;        if(ln>=0 && a[ln]>T.a[ln])            return true;        else            return false;    }    else        return false;}bool BigNum::operator>(const int &t)const  //大数和一个int类型的变量的大小比较{    BigNum b(t);    return *this>b;}void BigNum::print()   //输出大数{    int i;    printf("%d",a[len-1]);    for(i=len-2;i>=0;i--)        printf("%04d",a[i]);    printf("\n");}/*把5和5的倍数的数拿出来，并且将该位置替换成1这样0-9的最后一位非零数为：1 1 2 6 4 4 4 8 4 610-19最后一位非零数为：6 6 2 6 4 4 4 8 4 6可以看出将5拿出来之后可以发现规律令d[0......9]={1 1 2 6 4 4 4 8 4 6};那么d[n]=d[n%10]*6;这里*6操作实际上是×6取最后一位，所以从10往后每10为以循环然后就是5的倍数的方面了，5*10*15*20*25*30.....提取公因子之后就变成(5^p)*p!因为每一位都提出来一个5嘛，这里p=你要计算的值/5；每一次这个操作都必须要有p个2来把5给消掉，那么就需要p个2也就是2^p，然后就会得到：令f[n]表示的n的阶乘的最后一位非零数字就得到公式：f[n]=(d[n]/2^p)*f[p],我们发现：2^1%10=2，2^2%10=4，2^3%10=8，2^4%10=6，每四个一循环，当P==0的时候比较特殊，2^P%10=1除上2^P其实就是乘上2^(-P)，这样处理就简单了，根据循环的性质就可以将T[N]简化成T[N] = X[N] * 2^(-P) * T[P]，这样一来，算法的复杂度就只有O(log5(N))了。并且2是每四个一循环，2^(-P) = 2^(-P % 4 + 4)。*/int FindNoneZeroTail(BigNum Bn)//查找最后一位非零的数{    if(!Bn.len)        return 1;//0!=1    if(Bn.len==1)//如果是一位数的话    {        if(Bn.a[0]<5)//小于5的当然能直接输出了        {            return data[Bn.a[0]];        }        else if(Bn.a[0]<10)//其余的        {            //因为x/y=x*y(-1)次方，所以除以*TwoMod[2]就是除2            return data[Bn.a[0]]*TwoMod[2]%10;//这里面肯定只有一个5被拿出来了，所以只需要用一个2来消除5就行了        }    }    int v=Bn%10;    Bn=Bn/5;//这一层操作有这么多的5    int XN=data[v]*6%10;//当前数字阶乘的最后一位非零数字    int idx=4-Bn%4;    if(idx==0)    {        idx=4;    }    XN*=TwoMod[idx-1];    return  XN*FindNoneZeroTail(Bn)%10;}int main(){    freopen("C:\\Users\\acer\\Desktop\\in.txt","r",stdin);    BigNum a;    while(cin>>a)    {        printf("%d\n",FindNoneZeroTail(a));    }    return 0;}