概要

\(N\) 個のロッカーに対して、「\(i\) 回目の操作で \(i\) の倍数番目のロッカーを反転させる」という処理を \(N\) 回行った後、最終的に開いているロッカーの総数を求める問題です。

考察

各ロッカーが何回操作されるか

ロッカー \(k\) が操作されるのは、操作回数 \(i\) が \(k\) の約数であるときです。 例えば、ロッカー \(6\) は \(1, 2, 3, 6\) 回目の操作で状態が切り替わります。

最終的に開いている条件

ロッカーは最初閉まっており、操作のたびに「開く」と「閉じる」が入れ替わります。 - 操作回数が 奇数回 なら、最終的に 開いている - 操作回数が 偶数回 なら、最終的に 閉まっている

つまり、この問題は「\(1\) から \(N\) までの整数のうち、約数の個数が奇数であるものがいくつあるか」を数える問題に言い換えられます。

約数の個数が奇数になる数とは

通常、整数 \(k\) の約数は \(a \times b = k\) となるペア（例：\(6\) なら \(1 \times 6, 2 \times 3\)）で存在するため、個数は偶数になります。 しかし、完全平方数（\(1, 4, 9, 16, \dots\) のように、ある整数の \(2\) 乗で表される数）の場合だけは、\(a \times a = k\) というペアができるため、約数の個数が奇数になります。 - 例：\(4\) の約数は \(1, 2, 4\) の \(3\) 個（奇数） - 例：\(9\) の約数は \(1, 3, 9\) の \(3\) 個（奇数） - 例：\(16\) の約数は \(1, 2, 4, 8, 16\) の \(5\) 個（奇数）

したがって、求める答えは \(1\) 以上 \(N\) 以下の範囲にある完全平方数の個数 です。

素朴なアプローチの限界

\(N\) 回の操作を愚直にシミュレーションすると、計算量は \(O(N + \frac{N}{2} + \frac{N}{3} + \dots) \approx O(N \log N)\) となります。今回の制約は \(N \leq 10^{18}\) と非常に大きいため、シミュレーションでは到底間に合いません。数学的な性質を利用して \(O(1)\) またはそれに近い計算量で解く必要があります。

アルゴリズム

\(1\) から \(N\) までの間にある完全平方数は、\(1^2, 2^2, 3^2, \dots, m^2\) と表せます。 このとき \(m^2 \leq N\) を満たす最大の整数 \(m\) が、完全平方数の個数となります。

この \(m\) は、\(\sqrt{N}\) の小数点以下を切り捨てた値、すなわち \(N\) の整数平方根 です。 $\(m = \lfloor \sqrt{N} \rfloor\)$

計算量

• 時間計算量: \(O(\log (\log N))\)
  • math.isqrt などの整数平方根の計算は、ニュートン法などを用いて非常に高速に行われます。
• 空間計算量: \(O(1)\)

実装のポイント

• 大きな数の精度: \(N \leq 10^{18}\) という非常に大きな値を扱うため、浮動小数点数型の math.sqrt を使うと精度不足で誤差が出る可能性があります。Python 3.8 以降で利用可能な math.isqrt(n) は、整数演算のみで正確な整数平方根を計算してくれるため、この問題に最適です。

  ソースコード

import math

def main():
    # 入力を読み込む
    try:
        line = input().strip()
        if not line:
            return
        n = int(line)
        
        # ロッカー k が最終的に開いているのは、k の約数の個数が奇数のときです。
        # 自然数 k の約数の個数が奇数であることは、k が完全平方数であることと同値です。
        # したがって、1 から N までの間にある完全平方数の個数を求めればよいことになります。
        # これは floor(sqrt(N)) に等しいです。
        # Python 3.8 以降では math.isqrt を使用することで、大きな整数に対しても
        # 浮動小数点の精度問題を回避しながら整数平方根を計算できます。
        result = math.isqrt(n)
        
        # 結果を出力
        print(result)
    except EOFError:
        pass

if __name__ == '__main__':
    main()

---

この解説は gemini-3-flash-preview によって生成されました。