実際に問題文が要求する操作を行ってみましょう。

ロッカーが \(20\) 個あるとします。
\(i\) 個目のロッカーが空いていることを 1 、閉まっていることを 0 で表現し、ロッカーの状態を長さ \(20\) の 01 文字列で表すことにします。

• \(1\) 回目の操作で、ロッカーの状態は 11111111111111111111 となる。
• \(2\) 回目の操作で、ロッカーの状態は 10101010101010101010 となる。
• \(3\) 回目の操作で、ロッカーの状態は 10001110001110001110 となる。
• \(4\) 回目の操作で、ロッカーの状態は 10011111001010011111 となる。
• \(5\) 回目の操作で、ロッカーの状態は 10010111011010111110 となる。
• \(6\) 回目の操作で、ロッカーの状態は 10010011011110111010 となる。
• \(7\) 回目の操作で、ロッカーの状態は 10010001011111111010 となる。
• \(8\) 回目の操作で、ロッカーの状態は 10010000011111101010 となる。
• \(9\) 回目の操作で、ロッカーの状態は 10010000111111101110 となる。
• \(10\) 回目の操作で、ロッカーの状態は 10010000101111101111 となる。
• \(i\) ( \(11 \le i \le 20\) ) 回目 の操作で切り替わるロッカーは \(i\) のみです。
• 最終的に、開いた状態なのはロッカー \(1,4,9,16\) です。

上記の実験から分かることがあります。
最終的に開いたままのロッカーは、ロッカー番号 \(i\) がある整数 \(k\) を用いて \(i=k \times k\) と表せる時、またその時に限りそうです。
実は、この予想は正しいです。

証明の概略
ロッカー \(i\) の開閉が切り替わるのは、操作回数 \(j\) が \(i\) の約数の時、またその場合に限られます。
すると、ロッカー \(i\) の開閉が切り替わる回数と \(i\) の約数の個数とは等しいです。
最終的にロッカーが開いたままとなるのは \(i\) の約数が奇数個の時ですが、約数を奇数個もつ正整数の集合は正の平方数の集合と等しいです。

よって、 \(k \times k \le N\) を満たす最大の \(k\) を見つけることができれば、開いたままとなるロッカーは番号 \(1 \times 1, 2 \times 2, \dots, k \times k\) の \(k\) 個であることがわかります。
二分探索等を用いてそのような \(k\) を見つけてもよいですが、十分な精度で平方根が得られるプログラミング言語であればもう少し楽にそのような \(k\) の値を求めることができます。

• 答え \(k = \lfloor \sqrt{N} \rfloor\) が成り立ちます。
• \(\lfloor \sqrt{N} \rfloor\) の精度が完全に正しければこれでもよいですが、「だいたい正しいが、確実に正しいかは分からない」という場合に誤差を正しく補正する方法があります。
  

以下のアルゴリズムで補正すればよいです。

• \(k = \sqrt{N}\) を整数型に変換したものから始める。
• \(k \times k < N\) である限り、 \(k\) を増やし続ける。
  • こうすることで、この時点で確実に \(k \times k \ge N\) が成り立つ。
• \(k \times k > N\) である限り、 \(k\) を減らし続ける。
  • この終了時点で、必ず \(k \times k \le N\) を満たす最大の整数 \(k\) で停止する。この値は \(\lfloor \sqrt{N} \rfloor\) にも一致する。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;
using ll=long long;

int main(){
  ll N;
  cin >> N;
  ll d=sqrt(N);
  while(d*d<N){d++;}
  while(d*d>N){d--;}
  cout << d << "\n";
  return 0;
}