Overview

This is a problem of finding the number of lockers that are open after repeating the operations. The conclusion is that the only open lockers are “those whose numbers are perfect squares,” so the answer is the count of perfect squares from \(1\) to \(N\), which is \(\lfloor\sqrt{N}\rfloor\).

Analysis

Let’s think about how many times locker \(k\) has its state toggled.

• In the \(i\)-th operation, lockers that are “multiples of \(i\)” are toggled.
• Locker \(k\) is toggled when \(i\) is a divisor of \(k\) (i.e., \(i \mid k\)).

Therefore, the number of times locker \(k\) is toggled = the number of divisors of \(k\).

Since the initial state is “closed”: - If the toggle count is even → it remains closed at the end - If the toggle count is odd → it is open at the end

Here, the key property is:

• Normally, divisors come in pairs (e.g., the divisors of \(12\) pair up as \(1\times12, 2\times6, 3\times4\))
• However, only when \(k\) is a perfect square (e.g., \(9=3^2\)), \(\sqrt{k}\) pairs with itself, making the number of divisors odd

In other words, the only lockers that end up open are those with perfect square numbers.

Concrete example: When \(N=10\), the perfect squares are \(1, 4, 9\) — three in total, so 3 lockers are open.

A naive simulation would require iterating through multiples for each \(i\), resulting in approximately \(N(1/1+1/2+...+1/N) \approx N\log N\) total updates. Moreover, since \(N\) itself can be up to \(10^{18}\), this is practically impossible. By reducing the problem to counting perfect squares, it can be solved instantly.

Algorithm

1. Use the fact that only lockers with perfect square numbers are open.
2. Among \(1^2, 2^2, 3^2, \dots\), the count of those not exceeding \(N\) is \(\lfloor\sqrt{N}\rfloor\).
3. Therefore, output \(\lfloor\sqrt{N}\rfloor\) as the answer.

In Python, math.isqrt(N) accurately returns \(\lfloor\sqrt{N}\rfloor\) (the integer square root).

Complexity

• Time complexity: \(O(1)\)
• Space complexity: \(O(1)\)

Implementation Notes

• Since \(N \le 10^{18}\), using the floating-point sqrt may cause errors due to precision issues. Using math.isqrt(N) safely computes \(\lfloor\sqrt{N}\rfloor\).

  Source Code

import sys
import math

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

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.