階乘的0
時間限制:3000 ms | 內存限制:65535 KB
難度:3
描述
計算n!的十進制表示最後有多少個0
輸入
第一行輸入一個整數N表示測試數據的組數(1<=N<=100)
每組測試數據占一行,都只有一個整數M(0<=M<=10000000)
輸出
輸出M的階乘的十進制表示中最後0的個數
比如5!=120則最後的0的個數為1
樣例輸入
6
3
60
100
1024
23456
8735373樣例輸出
0
14
24
253
5861
2183837解題思路:因為在質數中,只有2和5相乘才會在尾部出現一個"0",那麼只要將m分解質因數,然後統計2和5的個數,其中較小的一個就是答案。
進一步來說,m分解質因數之後,2的個數絕對比5多,那麼問題進一步簡化,只要統計出所有的質因數中有多少個5即可。
例如:
5!=5*4*3*2*1=120,其中有1個5、1個2,所以最後有1個0
10!=10*9*8*7*6*5*4*3*2*1=3628800,連乘積可以寫成(5*2)*(3*3)*(2*2*2)*7*(3*2)*5*(2*2)*3*2*1,其中有2個5、8個2,因子5的個數即為最後0的個數,所以最後有兩個0
用比較笨的方法算一下:
1—>3000裡面5的倍數有:
5,10,15,25,……95,100,105,110,115,125,……195,200,……2995,3000
那麼5的個數是3000÷5=600(個)
而其中只要是5^2=25的倍數的數就能分解成2個5,例如:
25,50,75,100,125,150,175,200,225,……3000,這些數要算2個5,所以5的個數就要多加1次這些數的個數,
那麼在上面這堆數裡面25的個數是3000÷25=120(個)
而其中只要是5^3=125的倍數的數就能分解成3個5,例如:
125,250,375,……3000,這些數要算3個5,所以5的個數就又要多加1次這些數的個數
那麼在上面這堆數裡面125的個數是3000÷125=24(個)
而其中只要是5^4=625的倍數的數就能分解成4個5,例如:
625,1250,1875,2500,這4個數要算4個5,所以5的個數就又要多加1次這些數的個數
那麼在上面這堆數裡面125的個數是3000÷625=4.8,這裡實際就是只能有4個625的倍數了
所以5的個數實際是600+120+24+4=748(個)
[cpp]
#include<stdio.h>
int main()
{
int t,sum,n;
scanf("%d",&t);
while(t--)
{
sum=0;
scanf("%d",&n);
while(n)
{
n/=5;/*分解質因數,統計5的個數*/
sum+=n;
}
printf("%d\n",sum);
}
return 0;
}
#include<stdio.h>
int main()
{
int t,sum,n;
scanf("%d",&t);
while(t--)
{
sum=0;
scanf("%d",&n);
while(n)
{
n/=5;/*分解質因數,統計5的個數*/
sum+=n;
}
printf("%d\n",sum);
}
return 0;
}