P8622 [Lanqiao Cup 2014 National B] Biochip

Dr. X is studying a kind of biochip whose logic density and capacity are far higher than ordinary semiconductor chips. The doctor designs $n$ tiny light sources on the chip. Each time a light source is operated once, its state changes: on turns to off, or off turns to on. These light sources are numbered from $1$ to $n$. At the beginning, all light sources are off. Dr. X plans to perform the following actions on the chip: Operate once on all light sources whose indices are multiples of $2$, that is, turn on the light sources with indices $2,4,6,8,\cdots$. Operate once on all light sources whose indices are multiples of $3$, that is, operate on the light sources with indices $3,6,9,\cdots$. Note that at this time, light source $6$ is turned off again. Operate once on all light sources whose indices are multiples of $4$. ... Continue until operating once on all light sources whose indices are multiples of $n$. Dr. X wants to know: after these operations, which light sources in a certain interval are on.

Three integers separated by spaces: $N$, $L$, $R$. ($L < R < N < 10^{15}$) $N$ is the number of light sources, $L$ is the left boundary of the interval, and $R$ is the right boundary of the interval.

Output one integer, which is the number of light sources that are on in the interval $[L, R]$ after all operations.

Translated by ChatGPT 5