前往
大廳
主題

ZeroJudge - b836: kevin戀愛攻略系列題-2 說好的霸王花呢?? 解題心得

Not In My Back Yard | 2021-06-19 00:00:03 | 巴幣 0 | 人氣 224

題目連結:


題目大意:
輸入有多列,每列給定兩整數 n 、 m (0 < n ≦ 2147483647 , 0 ≦ m ≦ 2147483647),代表原本花朵有 n 枚花瓣。一開始拔一枚花瓣,之後的每次拔的花瓣數量都是上一次 + m 枚。試問是否可以剛好拔完。

如果可以剛好拔完,則輸出「Go Kevin!!」;反之輸出「No Stop!!」。



範例輸入:
9 2


範例輸出:
Go Kevin!!


解題思維:
可以看到這題等價於是在問:是否存在一整數 K ,使得
1 + (m + 1) + …… + (Km + 1) = n
根據類似這題的邏輯,可以看到上式可以寫為
(Km + 2)(K + 1) ÷ 2 = n
而這可以推得到
K = (sqrt((m + 2) ^ 2 + 8m(n - 1)) - (m + 2)) ÷ (2m)
將上式的值取整 ,再將該 K 值套回到 (Km + 2)(K + 1) ÷ 2 看是否等於 n 。

如果是就代表存在這樣子的整數 K (整數取整還是整數);反之,則不存在。




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

創作回應

更多創作