主題

ZeroJudge - d411: 算了好久...... 解題心得

Not In My Back Yard | 2018-08-14 16:34:56 | 巴幣 0 | 人氣 237

題目連結:

題目大意:
給定兩正整數M、N(0 ≦ M <10 ^ 9999,0 ≦ N<10),判斷M是否可被2 ^ 整除。

解題思維:
這題並非大數題,若要用大數當然也是可以,但實際上有更快、更簡潔的方法。

因為給一個十進位整數(其實任何進位也一樣),例如48763這個數字就可以寫作:
4 * 10 ^ 4+8 * 10 ^ 3+7 * 10 ^ 2+6 * 10 ^ 1+3 * 10 ^ 0
又由於餘數的性質,使得先取餘數、後取餘數都是等價的。

因此要判斷是否可被2 ^ N所整除,以上面48763的數字以及N=2為例:
先對4取餘數,得0 →
再放進8,變08(即8)。取餘數,得0 →
再放進7,得7。取餘數,得3 →
再放進6,變36,便得0 →
最後放進3,變為3,取最後一次餘數,於是得到了3這個最終結果。
但是餘數並不為0,因此我們知道了48763並無法被2 ^ 2整除。

以此類推,不管M多大,這套方法便可以確定我們所需的答案。


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

創作回應

相關創作

更多創作