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