駭客數學 基礎概念+數論 5題

[acdimns]

1.

IMAG0246_BURST002_1.jpg (7.32 KiB) 已瀏覽 7692 次

2.
下列乘積之末尾各有幾個0?
1000!

駭客的作法
[1000/5]+[1000/5^2]+[1000/5^3]+[1000/5^4]=200+40+8+1=249

1000!=1*2*3*4*...*999*1000 (是嗎?)
看過老師之前的回答:5 的次方是多少，即可知道 1000! 的末尾有幾個0
我不太明白,是指5,10,15,20......這些數總共有幾個嗎?
作法該如何解釋呢?

3.

IMAG0244_BURST002_1.jpg (8.52 KiB) 已瀏覽 7692 次

4.
2^20 －1 和 2^19 ＋1 的最大公因數為(A)1 (B)3 (C) 52 (D) 10
答案：B

網路解答:
2^20-1=2^19*2-1，令2^19=A，則2^20-1=2A-1.....(1)，2^19+1=A+1.......(2)
以輾轉相除法的原理來算，兩者之差為其最大公因數
A為未知數，設法令A消失，故(2)*2-(1)=3為二者之最大公因數

疑問:寫成輾轉相除法,答案應為-3不是嗎?

IMAG0243_1.jpg (8.1 KiB) 已瀏覽 7692 次

5.
設自然數n除以3餘2,除以5餘3,除以7餘2,若 n小於10000,試求符合條件的最大自然數n

網路解答:
從3跟5的條件來看
最小符合的數為8
每次增加15(因為要能被3跟5整除)
則23為最小能符合題意的正整數
所以23+15n<10000
→15n<9977→n<665.多
所以當n=665
即23+15*665=9998是為所求

疑問:
最小符合的數23後, 23+15n<10000
為什麼只考慮3,5的倍數15n呢?怎麼不用考慮7的倍數呢?

駭客數學解答:(請問圈起來是怎麼來的?)

IMAG0242_1.jpg (13.83 KiB) 已瀏覽 7692 次

這種題型蠻常出現,可是以上兩種作法都不甚了解,不知道老師有沒有其他可通用的做法?

[thepiano]

您有心把每個觀念都弄懂，很好，教學生時，也應如此要求他們！


第 1 題
請參考附件

第 2 題
舉個例子，250 = 2 * 5^3，我們可說 250 的質因數分解中，5 的次方是 3
然後只有一個 2，故其末尾僅有 1 個 0

1000! 很大，不可能真的把它質因數分解
其實它的質因數分解中，2 的次方比 5 的次方大
所以我們只要知道其質因數分解中，5 的次方是多少，即可知末尾有幾個 0

[1000/5] 是在算 1000 以內，5 的倍數有幾個
[1000/5^2] 是在算 1000 以內，25 的倍數有幾個
以 25 這個數為例，25 = 5^2，其 5 的次方是 2
在算 [1000/5] 時，25 算了 1 次，在算 [1000/5^2]，25 又算了 1 次，總共算了 2 次，這就是我們要的

由於 5^4 ＜ 1000 ＜ 5^5
故所求 = [1000/5] + [1000/5^2] + [1000/5^3] + [1000/5^4]

第 3 題
1 + 2 + 3 + 4 + 5 = 15
A + E + C + B + E + D = 15 + E
又 A + E + C = B + E + D
故 E 只能是奇數，故 E 有 3 種填法

第 4 題
因為 2^20 + 2 比 2^20 - 1 大
所以輾轉相除法一開始用 1 即可
減掉後剩 2^19 - 2，再用 2^19 - 2 除 2^19 + 1，就會是 3

但為何 2^19 - 2 是 3 的倍數呢？就留給您當習題！

第 5 題
(1) 此網路解答有考慮 7，但他沒有寫進算式，應該加上 9998/7 = 1428 ... 2，符合第 3 個條件

(2) 書上的解答用的是"中國剩餘定理"(有興趣的話，可自行 google 學習)
n = 105t + 21s + 2，已滿足除以 3 或 7 都餘 2，接下來只要讓它除以 5 餘 3 即可
若 s = 1，n = 105t + 23，除以 5 餘 3，到此已滿足所有條件，就可繼續做下去

但國小數學教甄都是考選擇題且分秒必爭，以上兩種方法有點慢，若是小弟來做這題，一定是偷懶一下
10000/7 = 1428 ... 4，故除以 7 餘 2 的最大 n 值為 9998
然後 9998 除以 5 餘 3 (看個位即知，不用真的除)，9998 除以 3 餘 2 (看各位數字和為 35 即知)，結束！

當然您也許認為小弟只是運氣好，第 1 個就找到
若是 9998 不符所求，其實您可接著考慮 9991、9984、9977、9970、....，一定可以很快得到答案

最後，小弟把題目改成：這樣的 n 有幾個(0＜n＜10000)？留給您當習題

[acdimns]

第 2 題
謝謝老師耐心的說明,我都看得懂,但我的腦筋有一個地方轉不過去,就是1000!=1*2*3*4*...*999*1000 跟質因數分解有什麼關係? 1*2*3*4*...*999*1000的過程中,…14*15*16…20*21...30,40,50...這些數也都會產生0, 怎麼只考慮5 的次方呢?

第 4 題第一句
2^20 + 2 比 2^20 - 1 大
是不是要改成2^20-1比2^19+ 1大?這樣我才有算出來…
為何 2^19 - 2 是 3 的倍數呢？我只會一個一個乘出答案來…為什麼?

第 5 題
謝謝老師的偷懶方法, 我也查了中國剩餘定理 http://www.youtube.com/watch?v=bFisuyRQEGk
這樣我就了解本題=128+105t
但還是不懂書中的寫法n = 105t + 21s + 2怎麼又有t又有s?
尤其是為什麼「使3式能滿足1式的條件」是怎麼變成→
(21s+2)/5=4s+(s+2)/5→這個式子從何而來?
想到有鑽牛角尖了,但很怕沒弄懂,下次遇到還是不會,謝謝老師!

這樣的 n 有幾個(0＜n＜10000)？
我用等差級數來算對嗎?
23+(n-1)105=9998
n=96

[thepiano]

第 2 題
14 * 15 * 16 = 3360 也會產生 0 沒錯，問題是您會想去乘嗎？

14 * 15 * 16 = 2^5 * 3 * 5 * 7，一看就知道有 1 個 5，所以會產生 1 個 0
當然我們也不可能真的去做質因數分解，而是只要知道它們裡面有 1 個 5 的倍數(即 15) 就可以了


第 4 題
2^20 - 1 本來就比 2^19 + 1 大，所以您才在輾轉相除法中，用 2^19 + 1(除數) 去除 2^20 - 1(被除數)
但您一開始用 2，得到 2^20 + 2，它比 2^20 - 1 大，所以不行，只能用 1

2^1 除以 3 餘 2
2^2 除以 3 餘 1
2^3 除以 3 餘 2
2^4 除以 3 餘 1
:
:
2^19 除以 3 餘 2
2^19 - 2 是 3 的倍數

第 6 題
會令 n = 105t + 21s + 2 是要保證 n 除以 3 和 7 都餘 2
接下來 n 除以 5 要餘 3
因為 105t 是 5 的倍數，所以只要讓 21s + 2 除以 5 餘 3 就行了

書上寫成 (21s + 2)/5 = [20s + (s + 2)]/5 = 4s + [(s + 2)/5]
然後讓 s + 2 = 3，就知道 s = 1 時，n 除以 5 餘 3
但寫這麼麻煩幹嘛，s = 1 代入 21s + 2 = 23，一看就知道它除以 5 餘 3 了

書上的方法及別人的方法(包括小弟的)都只能參考，不要太執著，多想想哪一種方法自己較易了解且能用於考試中

另外，這樣的 n 的確是 96 個沒錯

[acdimns]

老師說的對,都清楚了,謝謝~