每日演算法系列【LeetCode 319】燈泡開關

題目描述

初始時有個燈泡關閉。第輪，你打開所有的燈泡。第輪，每兩個燈泡你關閉一次。第輪，每三個燈泡切換一次開關（如果關閉則開啟，如果開啟則關閉）。第輪，每個燈泡切換一次開關。對於第輪，你只切換最後一個燈泡的開關。找出輪後有多少個亮著的燈泡。

示例1

輸入：  3  輸出：  1  解釋：  初始時, 燈泡狀態 [關閉, 關閉, 關閉].  第一輪後, 燈泡狀態 [開啟, 開啟, 開啟].  第二輪後, 燈泡狀態 [開啟, 關閉, 開啟].  第三輪後, 燈泡狀態 [開啟, 關閉, 關閉].    你應該返回 1，因為只有一個燈泡還亮著。

題解

首先有個燈泡，假設編號為到。第輪，所有編號是的倍數的燈泡被開關了一次。第輪，所有編號是的倍數的燈泡被開關了一次。類推下去，第輪，所有編號是的倍數的燈泡被開關了一次。

綜上，對於編號為的燈泡來說，它最終被開關的次數取決於有幾個因數。如果有奇數個因數，那麼它最後就是開著的，否則就是關著的。

那麼我們有一個定理：如果一個正整數有奇數個因數，那麼它一定是完全平方數。

最淺顯的證明就是，一個數的因數按照從小到大排個序，首尾兩兩一對之積一定等於。而如果因數只有奇數個，最中間一個因數只會出現一次，那麼。

嚴格證明也不難，首先將質因數分解為：

那麼的因數個數就是：

因為的因數個數是奇數，所以任意必定是奇數，即任意必定是偶數。

那麼就可以寫作：

這就證明了一定是一個完全平方數。

所以問題就轉化為了求到之間有多少個完全平方數。答案就是。

在具體實現的時候，為了防止出現浮點數誤差（比如算出來是，取整得到），我們可以計算的結果。

class Solution {  public:      int bulbSwitch(int n) {          return sqrt(n+0.5);      }  };