Count numbers X and Y of quiet days for vacations given by intervals [1;r] and [1;l-1].

The answer to the problem would be ANS=X-Y.
How to count X and Y?

In the first step,  we eliminate every 2th.

That is,  CNT_0=r and and CNT_1=r//2

In the second step,  CNT_2=CNT_1//3.

And so on.

Until CNT > 0.

Last non-zero  CNT is the answer.

Yes, but you should prove that the number of steps is short enough.
Here is some sketch of the proof. After deleting all 2nd numbers we are with $\frac{n}{2}$  numbers, after erasing all 3rd numbers we are with $\frac{2}{3}\cdot \frac{n}{2} = \frac{n}{3}$ numbers, after erasing all 4th numbers we are with $\frac{3}{4}\cdot \frac{n}{3} = \frac{n}{4}$ numbers and so on, after erasing every $k$-th number we are left with $\frac{n}{k}$ numbers, and we stop when $\frac{n}{k} < (k+1)\implies k \approx \sqrt{n}$, so after $O(\sqrt{n})$ steps the algorithm stops.

Edited by author 02.01.2021 20:07

Edited by author 02.01.2021 20:07

Edited by author 02.01.2021 20:09