題目：http://poj.org/problem?id=1218
給定一個正整數n(5<=n<=100)
現在獄卒喝醉了他會做n輪以下的事情：
第1輪，喝一點威士忌，把編號1,2,3,4,...的牢房打開
第2輪，喝一點威士忌，把編號2,4,6,8,...的牢房關起來
第3輪把3,6,9,12...的牢房開的關起來、關的打開
直到第n輪結束以後，獄卒就會暴斃，
然後牢房是開著的犯人就會趁機逃出來
問對每個n會有幾個犯人逃出來
程式碼：http://codepad.org/VyEwF6r9
數字很小，理論上可以直接模擬
但是仔細觀察一下發現，編號x的牢房要在最後是開著的狀態
條件是被操作奇數次，也就是有奇數個因數
想到了嗎？
就是完全平方數
問題就變成了1~n有幾個完全平方數
於是只要把n開根號、下取整，剛好就是答案
沒有留言:
張貼留言