---

懶人包: 質因數分解

 

--

 

題目的敘述又臭又長，但簡單來說：

 

有 n 種細胞， M = m1^m2 個瓶子；

每個細胞最一開始都是 1 個，每過一秒就會變成 Si 倍；

如果要能夠拿來做實驗，必須得讓那個細胞的總數能被瓶子的總數整除；

求最快能在多少時間內取得實驗用的樣本。

 

--

 

那怎麼才能知道最短時間呢?

 

你可以跑一個 while 循環，每次循環檢查是否能被 M 整除，然後愉快的吃 TLE......

 

因為有永遠無法整除這情況存在呢

且數字很大，大到超過 long long 的範圍，計算 30000 的 10000 次方顯然是不太理智的行為

所以我們需要更快、更簡單的方法，如果可以不用做大數運算更好

 

思考:

每個細胞最一開始都是 1 個，每過一秒就會變成 Si 倍

 

這段話翻譯成數學，把時間設為 t ，每秒就會有 Si^t 個細胞；

若 M 想要整除 Si^t ，則 Si^t 必須要包含 M 的所有質因數，漏一個都永遠無法整除。

 

不能想像嗎? 最簡單的例子就是

M=2
Si = 3

無論 Si 堆到幾次方，永遠都不可能被 2 整除

 

再換一組數字

M=12
Si=6

當 t=2 時，就可以被 M 整除了，因為 12 的質因數，6 都有

 

而我們只需要判斷質因數分解後，將兩數每個質因數的冪相除、再無條件進位，取最大值，就可以得到 t 的最小值。

以上面的例子來說

M = 12 = 2^2 * 3^1

Si = 6 = 2^1 * 3^1

2 的冪相除 = 2 / 1 = 2
3 的冪相除 = 1 / 1 = 1

取最大值 = 2

這就是答案

 

--

 

整體思路就是對每個數字都做質因數分解，包含一開始的 m1^m2

 

 

參考答案: gist(python)

自己看了都覺得有點醜的寫法