return n/10+(n%10>=k)+g(n/5,k);
}
int get(int n,int k)
{
if(n==0)return 0;
return get(n/2,k)+g(n,k);
}
int main()
{
int n,m;
while(~scanf("%d%d",&n,&m))
{
int res=1;
memset(cnt,0,sizeof(cnt));
cnt[2]=getpow(n,2)-getpow(n-m,2)-getpow(m,2);
cnt[5]=getpow(n,5)-getpow(n-m,5)-getpow(m,5);
cnt[3]=get(n,3)-get(n-m,3)-get(m,3);
cnt[7]=get(n,7)-get(n-m,7)-get(m,7);
cnt[9]=get(n,9)-get(n-m,9)-get(m,9);
cnt[3]+=cnt[9]*2;cnt[9]=0;
if(cnt[2]>cnt[5]){res*=mod2[(cnt[2]-cnt[5])%4];}
else if(cnt[2]
printf("%d\n",res%10);
}
return 0;
}
#include
#include
#include
using namespace std;
int cnt[8];
int mod2[4]={6,2,4,8};
int mod3[4]={1,3,9,7};
int mod7[4]={1,7,9,3};
int mod9[4]={1,9,1,9};
int getpow(int n,int k)
{
int sum=0;
while(n)
{
sum+=n/k;
n/=k;
}
return sum;
}
int g(int n,int k)
{
if(n==0)return 0;
return n/10+(n%10>=k)+g(n/5,k);
}
int get(int n,int k)
{
if(n==0)return 0;
return get(n/2,k)+g(n,k);
}
int main()
{
int n,m;
while(~scanf("%d%d",&n,&m))
{
int res=1;
memset(cnt,0,sizeof(cnt));
cnt[2]=getpow(n,2)-getpow(n-m,2)-getpow(m,2);
cnt[5]=getpow(n,5)-getpow(n-m,5)-getpow(m,5);
cnt[3]=get(n,3)-get(n-m,3)-get(m,3);
cnt[7]=get(n,7)-get(n-m,7)-get(m,7);
cnt[9]=get(n,9)-get(n-m,9)-get(m,9);
cnt[3]+=cnt[9]*2;cnt[9]=0;
if(cnt[2]>cnt[5]){res*=mod2[(cnt[2]-cnt[5])%4];}
else if(cnt[2]
printf("%d\n",res%10);
}
return 0;
}
最后看一个BT题ZOJ1222
这题在很多OJ上都有，只不过数量级很小，可以用上面的方法轻松ac，但是这题据说输入是一个字符串，可能有100+位，所以面对如此高精度大数，要用新的方法来解决。
思路不变，还是以2和5为核心，把每个数最后的尾数乘起来，只是由于数的极速扩大，我们不能用原来的递归求解了，要用到一个循环节：int mod[10]={1,1,2,6,4,4,4,8,4,6};这个表示从0乘到9（将5换为1）的非0尾数。当n<5时，直接输出mod[n].我们要去掉尾数0，就要去掉相同数量的2和5，我们发现2的个数是远远多于5的个数，并且因子2的数目是最多的，所以最后得到的结果一定是一个偶数，于是存在这样一个特殊的尾数除法：2/2=6,4/2=2,6/2=8,8/2=4。同时在除以2的个数时，还是由于2的个数比较多的原因，是存在一个除法的循环节的，循环节的长度为4.并且这10个尾数相乘为6，当n>10时，我们可以得到一个公式：
此时我们就可以应用这个公式进行求解了，值得注意的是n是一个非常大的数，在除以5的时候我们可以利用高精度除法。
[cpp]
#include
#include
#include
using namespace std;
char str[1001];
int mod[10]={1,1,2,6,4,4,4,8,4,6};
int a[1001];
int getAns(int cnt)
{
if(cnt==1&&a[0]<5)return mod[a[0]];
int res=0;
int w=a[0];
for(int i=cnt-1;i>=0;--i)
{
res=res*10+a[i];
a[i]=res/5;
res=res%5;
}
if(a[cnt-1]==0)--cnt;
int m=(a[1]*10+a[0])%4;
int tmp=getAns(cnt)*mod[w]*6%10;
while(m--)
{
if(tmp==2)tmp=6;
else if(tmp==6)tmp=8;
else tmp/=2;
}
return tmp;
}
int main()
{
while(~scanf("%s",str))
{
int len=strlen(str);
memset(a,0,sizeof(a));
for(int i=0;i
a[i]=str[len-1-i]-'0';
}
int ans=getAns(len);
printf("%d\n",ans);
}
return 0;
}
#include
#include
#include
using namespace std;
char str[1001];
int mod[10]={1,1,2,6,4,4,4,8,4,6};
int a[1001];
int getAns(int cnt)
{
if(cnt==1&&a[0]<5)return mod[a[0]];
int res=0;
int w=a[0];
for(int i=cnt-1;i>=0;--i)
{
res=res*10+a[i];
a[i]=res/5;
res=res%5;
}
if(a[cnt-1]==0)--cnt;
int m=(a[1]*10+a[0])%4;
int tmp=getAns(cnt)*mod[w]*6%10;
while(m--)
{
if(tmp==2)tmp=6;
else if(tmp==6)tmp=8;
else tmp/=2;
}
return tmp;
}
int main()
{
while(~scanf("%s",str))
{
int len=strlen(str);
memset(a,0,sizeof(a));
for(int i=0