poj 1401---求N!末尾0的个数,2的个数一定比5多,观察得来,0的产生即为2*5,去找这个阶乘一行里面5的个数即可

#include<stdio.h>
#include<stdlib.h> int main()
{
int T,N;
while(scanf("%d",&T)!=EOF)
{
int i;
for(i=0;i<T;i++)
{
int sum=0;
scanf("%d",&N);
while(N)
{
N/=5;
sum+=N;
}
printf("%d\n",sum);
}
}
return 0;
}

  假如有4个数,5*1      5*5*5     5*5*3      5*9

1.变成 5*n1       5*n2             5*n3           5*n4      有4个数是5的倍数

2.变成 5*n1       5*5*n5         5*5*n6        5*n4     有2个数是25的倍数

3.变成 5*n1      5*5*5            5*5*n6        5*n4     有1个数是125的倍数

以上是为了避免重复,一次只计算1层(1,2,3)

每次加上的5的个数实际上为右边的几个数

应该是数论的定理:对于阶乘N!,给定N,N/5为1到N间有多少个数是5的倍数

同样对于N/25,N/125

目的是将N/5+N/25+N/125...

如果有哪项为0,就sum为止

while(N)
{
sum+=N/;
N/=;
}

的解读:多个相加为,且每次均看为一个数除以5,sum叠加

N/5+N/25+N/125...可看为N/5+N1/5+N2/5

N1=N/5,N2=N1/5

循环体:每个值都是一个数除以5,而每个数相比较之前的数除了5

while(N)
{
sum+=N/5;
N/=5;
}

对于逻辑关系:

一个数如果是25的倍数,那么他一定是5的倍数,相反就不对,所以,这是他能一层一层来的支柱

上一篇:SSH架构


下一篇:HDU2571:命运(DP)