Re: [中學] 開門關門問題

[dewgrw (狗爸)]

※ 引述《joepo (小鬼)》之銘言：
: 題目是這樣的…
: 有1000個人、編號1~1000的門，
: 第一個人進去時將所有門都打開
: 第二個人進去時將所有2的倍數的門都關上
: 第三個人進去時將所有3的倍數的門都做相反動作
: （即打開的關上，關上的打開）
: 依此類推，當第1000個人都進入後，
: 有幾個門是開著的？

  不好意思把舊題目翻出來討論

  假設今天變成100個人與編號1~1000的門,其他條件都一樣
  答案還是完全平方數嗎?

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 219.85.142.170
推 KitWoolsey  :非，例如128因少被第128個人作動作,最後會是開的.
  所以例如編號101的門被打開之後,因為缺少第101個人動作,
  可以直接 => 編號101~1000的門都是打開的?
※ 編輯: dewgrw          來自: 219.85.140.5         (08/11 17:42)
→ ckchi       :也不是 當兩個數字不同時會變得很麻煩
→ ckchi       :就你說的case 其實是:
→ ckchi       :1~1000中，小於100的因數有奇數個 門是開的
→ ckchi       :反之 小於100的因數有偶數個 門會關起來
→ ckchi       :因此在 1~100 中只有完全平方數是開的
→ ckchi       :但101~1000就不一定了 (因為被扣掉的因素數量不一定
→ dewgrw      :也有考慮過這點,例如大於100的數之後,只要是質數,
→ dewgrw      :門就是開的!如果將100寫成質數乘積,做為因數來排列
→ dewgrw      :組合,會比較方便嗎?
推 ckchi       :難吧 因為多了個 "判斷因數是否大於100" 的動作
→ ckchi       :只能說 會變成沒辦法有個很快的計算方式
→ ckchi       :而是要一個數一個數check 這樣就失去題目本意了
→ ckchi       :拿150跟300為例
→ ckchi       :如果今天編號是到1000號 兩個都關的(非完全平方數)
→ ckchi       :但因為今天只有到100號
→ ckchi       :150: 1 2 3 5 6 10 15 25 30 50 75 (150)
→ ckchi       :150 少了一次操作 因此會變成開的
→ ckchi       :300: 1 2 3 4 5 6 10 12 15 20 25 30 50 60 75 100
→ ckchi       :    (150 300)
→ ckchi       :300 少了兩次操作 因為仍然是關的
→ dewgrw      :首先感謝ck大願意討論...一開始我也是想,該不會要慢
→ ckchi       :而寫成質因數分解最大的兩個問題在於：
→ ckchi       :1. 還是要一個數一個數分解判斷
→ dewgrw      :慢check大於100的每個數吧~~是不是有其他方法可以解
→ ckchi       :2. 分解完後 仍然要判斷哪些大於100
→ ckchi       :所以還是沒有辦法很快找出數量
→ ckchi       :嗯 雖然很打擊人 可是我覺得兩數不同可能沒辦法速解