首页 > 代码库 > 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; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。