程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> NYOJ 84 階乘的0 數論

NYOJ 84 階乘的0 數論

編輯:C++入門知識

階乘的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;
}

 


 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved