概要

\(N\) 個のロッカーに対して約数に関する操作を行った後、開いているロッカーの個数を求める問題です。結論として、\(N\) 以下の平方数の個数（つまり \(\lfloor\sqrt{N}\rfloor\)）が答えになります。

考察

重要な気づき：各ロッカーが何回切り替えられるか

ロッカー \(k\) の状態が切り替わるのは、\(i\) 回目の操作において \(k\) が \(i\) の倍数であるとき、つまり \(i\) が \(k\) の約数であるとき です。

したがって、ロッカー \(k\) は \(k\) の約数の個数だけ状態が切り替わります。

最終状態の判定

• 最初はすべて閉まっている
• 奇数回切り替わると → 開いている
• 偶数回切り替わると → 閉まっている

つまり、約数の個数が奇数であるロッカーが開いている ことになります。

約数の個数が奇数になる条件

通常、約数はペアで存在します。例えば \(12\) の約数は \((1, 12), (2, 6), (3, 4)\) のようにペアになり、約数の個数は偶数です。

しかし、平方数の場合だけ、\(\sqrt{k} \times \sqrt{k} = k\) となり、\(\sqrt{k}\) はペアを作らず単独で存在します。

例：\(9\) の約数は \(1, 3, 9\) で、\(3 \times 3 = 9\) なので \(3\) は単独。約数は \(3\) 個（奇数）。

結論

\(N\) 以下で開いているロッカーの番号は \(1, 4, 9, 16, 25, \ldots\) つまり平方数です。

\(N\) 以下の平方数の個数は \(\lfloor\sqrt{N}\rfloor\) 個です。

素朴なアプローチが使えない理由

\(N \leq 10^{18}\) と非常に大きいため、各ロッカーをシミュレーションする \(O(N)\) や \(O(N \log N)\) のアプローチでは到底間に合いません。上記の数学的考察により \(O(1)\) で解く必要があります。

アルゴリズム

1. 入力 \(N\) を受け取る
2. \(\lfloor\sqrt{N}\rfloor\) を計算する（Python では math.isqrt(N) を使用）
3. その値を出力する

計算量

• 時間計算量: \(O(1)\)（平方根の計算のみ）
• 空間計算量: \(O(1)\)

実装のポイント

• math.isqrt() を使用する理由: \(N\) が最大 \(10^{18}\) と非常に大きいため、int(math.sqrt(N)) では浮動小数点の精度問題で誤差が生じる可能性があります。math.isqrt() は整数演算で正確に整数平方根を計算してくれるため、大きな数でも安全です。

• 具体例での確認: \(N = 10\) の場合

  • ロッカー \(1\): 約数 \(\{1\}\) → \(1\) 回 → 開
  • ロッカー \(2\): 約数 \(\{1, 2\}\) → \(2\) 回 → 閉
  • ロッカー \(3\): 約数 \(\{1, 3\}\) → \(2\) 回 → 閉
  • ロッカー \(4\): 約数 \(\{1, 2, 4\}\) → \(3\) 回 → 開
  • ロッカー \(9\): 約数 \(\{1, 3, 9\}\) → \(3\) 回 → 開

開いているのは \(1, 4, 9\) の \(3\) 個 = \(\lfloor\sqrt{10}\rfloor = 3\) ✓

ソースコード

import math

N = int(input())
print(int(math.isqrt(N)))

---

この解説は claude4.5opus によって生成されました。