| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
囧了,自己乱写居然过了。。。大家看看这样写貌似不对吧。。。
#include<stdio.h>
int n,m;
int div[10][10];
const int di[20][3]={{1,1,1},{3,1,3},{7,1,7},{9,1,9},
{1,3,7},{1,7,3},{1,9,9},
{3,3,1},{3,7,9},{3,9,7},
{7,3,9},{7,7,1},{7,9,3},
{9,3,3},{9,7,7},{9,9,1}};
void add(int n,int d,int &sum,bool ad) //计算n!里面包含多少个因子d
{
while(d<=n)
{
if(ad)
sum+=(n/=d);
else
sum-=(n/=d);
}
}
//就是这里。。。下面函数本意是那样,但是貌似这样做不对,用100 10这组数据就不对了
void add2(int n,int &ans,bool add) //计算n!除掉2和5之后的尾数,add时乘进ans中,false时ans/尾数。
{
int i;
for(;n>=20;n/=5)
{
for(i=n%20;i;i--)
{
if((i%5)&&(i%2))
{
if(add)ans*=i,ans%=10;
else ans=div[ans%10][i%10];
}
}
}
for(i=n%20;i;i--)
{
int p=i;
while(!(p%5))p/=5;
while(!(p%2))p/=2;
if(add) ans*=p,ans%=10;
else ans=div[ans%10][p%10];
}
}
void init2()
{
for(int i=0;i<16;i++)
div[di[i][0]][di[i][1]]=di[i][2];
//div[a][b]=c表示,a=b*c%10,即尾数为a的除以尾数为b的,等于尾数为c的(但是仅适用于a,b,c为(1,3,7,9)时)
}
int main()
{
init2();
//printf("%d %d %d %d\n",di[15][0],di[15][1],di[15][2],div[di[15][0]][di[15][1]]);
while(scanf("%d%d",&n,&m)!=EOF)
{
/* if(n==0&&n==0)
printf("0\n");*/
int i;
int sum2=0,sum5=0,ans=1;
//下面计算质因子2和5
add(n,2,sum2,true);add(n,5,sum5,true);
add(m,2,sum2,false);add(m,5,sum5,false);
add(n-m,2,sum2,false);add(n-m,5,sum5,false);
if(sum5>sum2)
{
printf("5\n");
continue;
}
else
sum2-=sum5;
add2(n,ans,true);
add2(m,ans,false);
add2(n-m,ans,false);
//下面乘上剩余的2
if(sum2>=4) ans*=6,ans%=10; //由于2*2*2*2=16,尾数为6,而6*6%10=6,所以无论存在多少个2,模4再乘上6即可
for(i=sum2%4;i;i--) //乘2
{
ans<<=1;
ans%=10;
}
printf("%d\n",ans);
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator