#P10565. Recursive Lights Toggle
Recursive Lights Toggle
Recursive Lights Toggle
You are given a row of n lights numbered from 1 to n which are initially off. You perform a series of operations defined recursively as follows:
For each light i (from 1 to n in order), you perform the function press(i)
which does the following:
[
\text{press}(x): \quad \begin{cases}
\text{toggle light } x \quad (0 \to 1 \text{ or } 1 \to 0),
\text{for every } y \text{ such that } x\mid y \text{ and } x < y \le n, \text{ call } \text{press}(y).
\end{cases}
]
The entire process is performed by calling press(i)
for all i from 1 to n (i.e. in order, unconditionally).
For example, consider n = 4. The operations when calling press(1)
are as follows:
- Call
press(1)
: toggle light 1 (it becomes on). Then for every j with 1|j and 1 < j ≤ 4, callpress(j)
in order. - When
press(1)
callspress(2)
: toggle light 2 (it becomes on) and then for every j with 2|j and 2 < j ≤ 4, callpress(j)
. In this case,press(2)
callspress(4)
(toggling light 4 on). - Back in the call of
press(1)
: nextpress(1)
callspress(3)
, toggling light 3 on. (No further call since 3×2=6 > 4.) - Then
press(1)
callspress(4)
directly, toggling light 4 again (so it turns off).
After the call of press(1)
, later the outer loop still calls press(2)
, press(3)
, and press(4)
unconditionally. A careful simulation of the recursive calls shows that every light with index greater than 1 is toggled an even number of times, while light 1 is toggled exactly once. Hence, after all operations:
- Light 1 is on (since it is toggled once).
- Every light from 2 to n is off (since they are toggled an even number of times).
Your task is: Given two integers n and k, determine whether light k is on or off after performing all the operations.
inputFormat
The input consists of a single line containing two space‐separated integers n and k (1 ≤ k ≤ n ≤ 109).
outputFormat
Output a single line: ON
if the k-th light is on after all operations, and OFF
otherwise.
Note: Based on the process described, a complete simulation shows that the first light is toggled an odd number of times (and hence is on), while every other light is toggled an even number of times (and hence remains off). Therefore, the answer is ON
if and only if k = 1.
sample
1 1
ON