首页 > 代码库 > hdu1066

hdu1066

先把最后全部的0去掉,方法就是在乘的时候统计因子2的个数,然后每遇到一个5。就去掉一个,那么乘出来就没有最后的0了~然后在乘的时候仅仅保留最后一位就能够了,最后把统计了的2的个数乘回去(在统计的时候把2给提出来。这样就能够避免模的除法了!)

/** \brief hdu 1066
 *
 * \param date 2014/7/25
 * \param state AC
 * \return
 *
 */

#include <iostream>
#include <cstring>
#include <fstream>

using namespace std;

const int MAXN=10000;

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[MAXN],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()
{
    //cout << "Hello world!" << endl;
    //freopen("input.txt","r",stdin);
    char input[MAXN];
    while(scanf("%s",input)!=EOF)
    {
        cout<<lastdigit(input)<<endl;
    }
    return 0;
}


hdu1066