發表文章

目前顯示的是有「質因數分解」標籤的文章

<我有你沒有,你有我沒有,之到底誰有誰沒有?接著討論的(二)>

圖片
快起床~第二篇要來惹!!! 圖/yeowatzup @ Wikimedia Commons 前情提要 <我有你沒有,你有我沒有,之到底誰有誰沒有?來不及打完的(一)> 在開始之前... 來談談乘法公式 還記得國小的 分配律 嗎? ( a + b )  ×  c = ( a  ×  c ) + ( b  ×  c ) = ac + bc 上了國中後,分配律一轉眼就成了 乘法公式 , ( a + b )  ×  ( c + d ) = ( a  ×  ( c + d ) ) + ( b  ×  ( c + d ) ) = ( a  ×  c ) + ( a  ×  d ) + ( b  ×  c ) + ( b  ×  d ) = ac + ad + bc + bd 接著,換 和的平方 的公式登場, 然後,自己動手試試看 和的立方 呢? 補充: 展開的過程中,可以發現, 如果任意的乘開,很可能在過程中漏乘了幾項 ,然而,如果我們能以一個有系統的方式乘開,也就是找到一個乘開的方法(順序),便可以確保展開的過程中沒有遺漏的項目!這兒的方法是 由左至右,由a至b 。所以括號由左至右都先挑a出來乘,乘出aaa。接著,再一次地由左至右都挑a,當挑到第三個括號時,如果一樣挑a,那麼便與前一個相乘方法相同,故這一次挑b,乘出aab,以此類推。 啊,岔題遠了。 來幾個特別的案件吧! 讓我們將 和的立方 中的 a 換成 1 而 b 換成 x 會變成什麼呢。 每個括號內都挑一個出來乘,不是1就是x ,可以看到最後展開的結果,有挑出3個x的(x^3,也就是x的三次方),有挑出2個x的(x^2,也就是x的平方),和挑出1個x的,以及都不挑x的(常數項)。 再看一個案件... (1+a)(1+b)(1+c) 將 和的立方 中的x換成a、b、c ,再根據 和的立方 的乘開方式,可以預料到, 展開後的結果會有a、b、c中只挑1個的,有a、b、c中挑2個的,以及a、...

<我有你沒有,你有我沒有,之到底誰有誰沒有?來不及打完的(一)>

圖片
腦袋嗎? 圖/Mgmoscatello @ Wikimedia Commons 腦袋嗎? 互質 啦! 什麼是互質? 如果兩個正整數(這兒僅簡單討論正整數)的最大公因數是1,則這兩個數互質。也就是兩個數沒有(除了1以外的)共同的因數,換句話說,正整數A的因數不會出現在B裏頭,反之亦然。 從小到大一定有寫過一種題目,通常長這樣,請問在...之內與...互質的數有幾個? 確切來說,舉個例子,請問在25內與30互質有幾個? 於是乎開始列出1到25,然後一個一個檢查,反正也才25個嘛~ 1跟30,2跟30,3跟30,4跟30,5跟30,6跟30,7跟30, 哦哦 ,8跟30,blablabla... 在後來我們發展出新的檢索方式來加速檢查的速度, 質因數分解 。 這個我會讓我來~ 圖/ Ron Armstrong @ Wikimedia Commons 透過短除法,可以得到30的質因數分解如下: 然後回到1至25,便可以馬上 剔除不與30互質的數字 ,也就是2的倍數、3的倍數以及5的倍數。因為,當該數字為2的倍數時,該數字與30便至少有2為他們的公因數。3的倍數與5的倍數,同理。 再進階些,可以使用 排容原理 : 我們讓圖中A、B、C區塊分別代表25裏頭2的倍數、3的倍數以及5的倍數,是故,A與B的交集(紅色與藍色的重疊區塊)即是那些同時為2的倍數也是3的倍數的那些數字,比如說6、12、18、24,可以發現,也就是6的倍數。 所以,計算25以內與30互質的個數,除了一個個檢查互質以外,也可以透過反面的想法,剔除所有不互質的數,剩下的便是與30互質的數了! 從上圖可以發現,整個不互質的數的區塊為(A區塊+B區塊+C區塊)再扣除重疊的(A與B區塊)、(A與C區塊)以及(B與C區塊)最後再加回(A與B與C區塊),也就是... |A|+|B|+|C|-|A∩B|-|A∩C|-|B∩C|+|A∩B∩C| 實際上操作看看: |A|=25以內2的倍數個數=(25 ÷2)取整數=12 |B|=25以內3的倍數個數=(25 ÷3)取整數=8 |C|=25以內5的倍數個數=(25 ÷5)取整數=5 |A∩B| =25以內6的倍數個數=(25 ÷6)取整數=4 |A∩C| =25...