這題給了一個數字n

對於一個固定的數字K，第K個路燈在n改變時的結果

case n<K: K路燈不存在，不考慮

case n=K: K路燈的狀態會改變K的因數次(因數包含1)

case n>K: K路燈的狀態會改變K的因數次(因數包含1)，因為對於第t趟(t>K)都無法對K路燈造成變化，所以對於第K路燈的最終結果和n=K的情況是一樣的

所以，根據上述，只要計算所有的K<n符合K的因數為奇數(狀態才不會被抵銷)的個數即為正確答案

但正常情況下因數都是倆倆一對的

以12舉例: 

1 2 3 4 6 12

1*12 = 2*6 = 3*4

若對於一個數m有一個單獨存在的因數，存在一個不成對的因數i

則m/i一定等於i (因為如果不等於i的話因數i會成對)

即 i*i = m

故m必為完全平方數

所以題目變成了 "給定一個數字n，求比n小的所有完全平方數"

即 根號n(向下取整)

QED.

如果有更嚴謹更短的證明請告訴我，也歡迎指出我可能存在的邏輯漏洞