概要

操作を繰り返したあとに開いているロッカーの個数を求める問題です。結論として、開いているロッカーは「番号が平方数のもの」だけなので、答えは \(1\) から \(N\) までの平方数の個数、つまり \(\\lfloor\\sqrt{N}\\rfloor\) になります。

考察

ロッカー \(k\) が何回状態を切り替えられるかを考えます。

• \(i\) 回目の操作では「\(i\) の倍数」のロッカーが切り替わります。
• ロッカー \(k\) が切り替わるのは、\(i\) が \(k\) の約数のとき（\(i \\mid k\)）です。

よって、ロッカー \(k\) が切り替わる回数 = \(k\) の約数の個数になります。

初期状態は「閉」なので、 - 切り替え回数が 偶数 → 最後も閉 - 切り替え回数が 奇数 → 最後は開

ここで重要な性質として、

• ふつう約数はペアになります（例：\(12\) の約数は \(1\\times12, 2\\times6, 3\\times4\) のように組になる）
• ただし \(k\) が平方数（例：\(9=3^2\)）のときだけ、\(\\sqrt{k}\) が自分自身とペアになり、約数の個数が奇数になります

つまり、最終的に開いているのは平方数番のロッカーだけです。

具体例：\(N=10\) のとき、平方数は \(1,4,9\) の3つなので、開いているロッカーは3個です。

素朴にシミュレーションすると、各 \(i\) で倍数をたどる必要があり、合計でおおよそ \(N(1/1+1/2+...+1/N) \\approx N\\log N\) 回の更新になってしまい、さらに \(N\) 自体が最大 \(10^{18}\) なので現実的に不可能です。
平方数の個数に帰着することで一瞬で解けます。

アルゴリズム

1. 開いているロッカーは平方数番のみであることを利用する。
2. \(1^2, 2^2, 3^2, \\dots\) のうち \(N\) 以下の個数は \(\\lfloor\\sqrt{N}\\rfloor\)。
3. よって答えとして \(\\lfloor\\sqrt{N}\\rfloor\) を出力する。

Pythonでは math.isqrt(N) が \(\\lfloor\\sqrt{N}\\rfloor\)（整数平方根）を正確に返します。

計算量

• 時間計算量: \(O(1)\)
• 空間計算量: \(O(1)\)

実装のポイント

• \(N \\le 10^{18}\) なので、浮動小数点の sqrt を使うと誤差でズレる可能性があります。math.isqrt(N) を使うと安全に \(\\lfloor\\sqrt{N}\\rfloor\) を求められます。

  ソースコード

import sys
import math

def main():
    N = int(sys.stdin.readline().strip())
    print(math.isqrt(N))

if __name__ == "__main__":
    main()

---

この解説は gpt-5.2-high によって生成されました。