Overview

Given \(N\) lockers, we perform \(N\) operations where “the \(i\)-th operation toggles every locker whose number is a multiple of \(i\).” The problem asks for the total number of lockers that are open after all operations.

Analysis

How many times is each locker toggled?

Locker \(k\) is toggled when the operation number \(i\) is a divisor of \(k\). For example, locker \(6\) is toggled during operations \(1, 2, 3, 6\).

Condition for a locker to be open at the end

All lockers start closed, and each operation toggles between “open” and “closed.” - If the number of operations is odd, the locker is ultimately open - If the number of operations is even, the locker is ultimately closed

In other words, this problem can be rephrased as: “Among the integers from \(1\) to \(N\), how many have an odd number of divisors?”

Which numbers have an odd number of divisors?

Normally, the divisors of an integer \(k\) come in pairs \((a, b)\) where \(a \times b = k\) (e.g., for \(6\): \(1 \times 6, 2 \times 3\)), so the number of divisors is even. However, for perfect squares (\(1, 4, 9, 16, \dots\), i.e., numbers that can be expressed as the square of some integer), there exists a pair \(a \times a = k\), which causes the number of divisors to be odd. - Example: \(4\) has divisors \(1, 2, 4\) — \(3\) divisors (odd) - Example: \(9\) has divisors \(1, 3, 9\) — \(3\) divisors (odd) - Example: \(16\) has divisors \(1, 2, 4, 8, 16\) — \(5\) divisors (odd)

Therefore, the answer is the number of perfect squares in the range from \(1\) to \(N\).

Limitations of the naive approach

If we naively simulate all \(N\) operations, the computational complexity is \(O(N + \frac{N}{2} + \frac{N}{3} + \dots) \approx O(N \log N)\). Given the constraint \(N \leq 10^{18}\), which is extremely large, simulation is far too slow. We need to leverage mathematical properties to solve this in \(O(1)\) or near-\(O(1)\) time.

Algorithm

The perfect squares from \(1\) to \(N\) can be listed as \(1^2, 2^2, 3^2, \dots, m^2\). The largest integer \(m\) satisfying \(m^2 \leq N\) is the number of perfect squares.

This \(m\) is the value of \(\sqrt{N}\) with the fractional part truncated, i.e., the integer square root of \(N\). $\(m = \lfloor \sqrt{N} \rfloor\)$

Complexity

• Time complexity: \(O(\log (\log N))\)
  • Integer square root computation using functions like math.isqrt is performed very efficiently using methods such as Newton’s method.
• Space complexity: \(O(1)\)

Implementation Notes

• Precision with large numbers: Since \(N \leq 10^{18}\) is a very large value, using the floating-point math.sqrt may produce errors due to insufficient precision. math.isqrt(n), available since Python 3.8, computes the exact integer square root using only integer arithmetic, making it ideal for this problem.

  Source Code

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()

---

This editorial was generated by gemini-3-flash-preview.