題目連結:
題目大意:
輸入有多列,每列給定兩整數 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 (整數取整還是整數);反之,則不存在。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。