內容有引用https://www.796t.com/content/1549394293.html
證明:
末尾0的個數就是指這個數總共有幾個10冪次
一個n!的數中 2的因子一定遠大於 5的因子
=> 只要算出 n!有幾個5
用一個簡單的遞迴
EX.
int f( int x ) {
if( x < 5 ) return 0 ;
else {
x /= 5 ;
return x + f(x) ;
}
}
f(5) = 1 + f(1) = 1 + 0 = 1
f(10) = 2 + f(2) = 2 + 0 = 2
f(20) = 4 + f(4) = 4 + 0 = 4
f(100) = 20 + f(20) = 20 + 4 + f(4) = 20 + 4 + 0 = 24
f(1000) = 200 + f(200) = 200 + 40 + f(40) = 240 + 8 + f(8) = 248 + 1 + f(1) = 249 + 0 = 249
內容有引用https://www.796t.com/content/1549394293.html
證明:
末尾0的個數就是指這個數總共有幾個10冪次
一個n!的數中 2的因子一定遠大於 5的因子
=> 只要算出 n!有幾個5
用一個簡單的遞迴
EX.
int f( int x ) {
if( x < 5 ) return 0 ;
else {
x /= 5 ;
return x + f(x) ;
}
}
f(5) = 1 + f(1) = 1 + 0 = 1
f(10) = 2 + f(2) = 2 + 0 = 2
f(20) = 4 + f(4) = 4 + 0 = 4
f(100) = 20 + f(20) = 20 + 4 + f(4) = 20 + 4 + 0 = 24
f(1000) = 200 + f(200) = 200 + 40 + f(40) = 240 + 8 + f(8) = 248 + 1 + f(1) = 249 + 0 = 249
f(5)=5//(5**1)
f(10)=5//(5**1)
f(25)=5//(5**1)+5//(5**2)
f(100)=5//(5**1)+5//(5**2)
f(125)=5//(5**1)+5//(5**2)+5//(5**3)
f(625)=5//(5**1)+5//(5**2)+5//(5**3)+5//(5**4)
f(1000)=5//(5**1)+5//(5**2)+5//(5**3)+5//(5**4)
內容有引用https://www.796t.com/content/1549394293.html
證明:
末尾0的個數就是指這個數總共有幾個10冪次
一個n!的數中 2的因子一定遠大於 5的因子
=> 只要算出 n!有幾個5
用一個簡單的遞迴
EX.
int f( int x ) {
if( x < 5 ) return 0 ;
else {
x /= 5 ;
return x + f(x) ;
}
}
f(5) = 1 + f(1) = 1 + 0 = 1
f(10) = 2 + f(2) = 2 + 0 = 2
f(20) = 4 + f(4) = 4 + 0 = 4
f(100) = 20 + f(20) = 20 + 4 + f(4) = 20 + 4 + 0 = 24
f(1000) = 200 + f(200) = 200 + 40 + f(40) = 240 + 8 + f(8) = 248 + 1 + f(1) = 249 + 0 = 249f(5)=5//(5**1)
f(10)=5//(5**1)f(25)=5//(5**1)+5//(5**2)
f(100)=5//(5**1)+5//(5**2)
f(125)=5//(5**1)+5//(5**2)+5//(5**3)
f(625)=5//(5**1)+5//(5**2)+5//(5**3)+5//(5**4)
f(1000)=5//(5**1)+5//(5**2)+5//(5**3)+5//(5**4)
打太快 修正一下
f(5)=5//(5**1)
f(10)=10//(5**1)
f(25)=25//(5**1)+25//(5**2)
f(100)=100//(5**1)+100//(5**2)
f(125)=125//(5**1)+125//(5**2)+125//(5**3)
f(625)=625//(5**1)+625//(5**2)+625//(5**3)+625//(5**4)
f(1000)=1000//(5**1)+1000//(5**2)+1000//(5**3)+1000//(5**4)