切換
舊版
前往
大廳
主題

ZeroJudge - d775: NOIP2009 3.細胞分裂 解題心得

Not In My Back Yard | 2020-10-13 00:12:19 | 巴幣 2 | 人氣 160

題目連結:


題目大意:
輸入第一列給定一正整數 N (1 ≦ N ≦ 10000),代表細胞的種類。

輸入第二列給定兩正整數 m1 、 m2 (1 ≦ m1 ≦ 30000 , 1 ≦ m2 ≦ 10000),代表試管有 m1 ^ m2 根。

最後一列給定 N 個正整數 Si (1 ≦ Si ≦ 2 × 10 ^ 9),代表其中一種細胞,其每個每秒會分裂為 Si 個同種細胞。

現在要從 N 種細胞的其中一種挑一個細胞出來繁殖。試問是否有一種細胞使得在開始後 K 秒(K 要盡量小),可以使得細胞總數被 m1 ^ m2 整除?如果有的話,且如果有多種可行的細胞,輸出最小的 K 值;反之,如果沒有任何細胞滿足此條件,則輸出「-1」。



範例輸入:
輸入範例 1:
1
2 1
3

輸入範例 2:
2
24 1
30 12


範例輸出:
輸出範例 1:
-1

輸出範例 2:
2


解題思維:
首先,如果 m1 = 1 ,則不用作以下的動作,因為拿任意一種的細胞都是可行的。而且 K = 0,因為剛拿到一個細胞就滿足所需了,因此輸出「0」。



如果 m1 ≠ 1 ,則將 m1 質因數分解,分解為 P1 ^ C1 × P2 ^ C2 …… 之形式,其中 Pi 為一質數且 Ci > 0。 再來,將剛剛的 C1 、 C2 、 …… 每個數字都乘以 m2。這樣就是 m1 ^ m2 的質因數分解。



接著對於每種細胞的 Si 值,依序除除看上面的 p1 、 p2 等等。如果 Si 無法被某個 Pj 整除,則代表這個細胞不管過多久、繁衍多少出來都無法被 m1 ^ m2 整除(因為 Si 沒有 Pj 這個質因數);

如果可以整除,就除到無法整除為止。過程中除的次數(假設為 D 次)即代表 Si 這個數字包含了 Pj 的 D 次方之因數。而 ceil(D ÷ Cj) (ceil() 代表向上取整,對於正整數等價於無條件進位)代表著對於這個質因數,此種細胞需要多少秒(第 T 秒的細胞數為 S ^ T)才可以達到或是超過 Cj 之值。

而將上式每個 Pj 求出的 ceil(D ÷ Cj) 之值當中取出最大的,即代表該種細胞需要至少多少秒才可以繁衍到被 m1 ^ m2 整除。



然後將每個細胞求出的至少所需秒數之中取出最小的,即是所求的最小 K 值。如果所有細胞不管經過多長的時間都不能被 m1 ^ m2 整除,此時輸出「-1」。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作