ICPC 2557 The Drunk Jailer

題意說給了N道門，某男會做如下事件N次﹕
在第i次中，把i, 2i, 3i. . . 的門做手腳。如果該門是鎖著的，他會解鎖；否則重新把它鎖上。
問，有多少道門是解鎖？假設一開始所有門都是鎖上的。

由於N少於100，故以簡單的枚舉即可通過。在這裡不妨給大家另一種解題思路。

想想第i道門會被某男遇上多少次呢？答案顯然是i的因數總數。
我們知道當門被遇上偶數次，門最後必然被鎖上。但，問何時才會遇上奇數遍？

若把N寫成a x b，肯定如果在第a會遇上次門，第b次會同樣遇上。
因為如此，除非a = b，否則門必然被訪問偶數遍。
得出結論﹕只有平方數的門才會被某男訪問奇數遍。

問題轉化成﹕給出N，問有多少平方數少於等於N。
輕鬆解決。