首页 > 代码库 > NYOJ1026 阶乘末尾非0 【模板】

NYOJ1026 阶乘末尾非0 【模板】

阶乘末尾非0

时间限制:2000 ms  |  内存限制:65535 KB
难度:3
描述
我们的问题很是简单,n!末尾非0数是几?
比如n=5的时候,n!=120,那么n!末尾非0数是2.
输入
多组数据,
每组数据占一行,每行一个整数0<=n<=10^1000
输出
n!末尾非0数。
样例输入
5
样例输出
2

直接用的网上的模板

/*==================================================*| 阶乘最后非零位,复杂度 O(nlogn)
\*==================================================*/
//返回该位, n 以字符串方式传入
#include <string.h>
#include <stdio.h>
#define MAXN 10000
int a[MAXN];
char str[MAXN];
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 lastdigit(char* buf){
	int len=strlen(buf),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(){
	while(scanf("%s", str) == 1){
		printf("%d\n", lastdigit(str));
	}
	return 0;
}