阶乘最后非零位

showproblem.php?pid=1066

 1 #include<cstdio>
 2 #include<cstring>
 3 const int M=1024;
 4 const int tomod[20]= {1,1,2,6,4,2,2,4,2,8,4,4,8,4,6,8,8,6,8,2};
 5 int lastdigit(char buf[]){//阶乘最后非0位O(nlogn)返回该位,n以字符串方式传入
 6     int len=strlen(buf),ret=1,a[M];
 7     if(len==1) return tomod[buf[0]-'0'];
 8     for(int i=0;i<len;i++) a[i]=buf[len-1-i]-'0';
 9     for(;len;len-=!a[len-1]){
10         ret=ret*tomod[a[1]%2*10+a[0]]%5;
11         for(int c=0,i=len-1;i>=0;i--){
12             c=c*10+a[i];
13             a[i]=c/5;
14             c%=5;
15         }
16     }
17     return ret+ret%2*5;
18 }
19 char str[M];
20 int main() {
21     while(~scanf("%s",str)) {
22         printf("%d
",lastdigit(str));
23     }
24     return 0;
25 }

View Code

end