Due to the floor function many values will remain the same.
Thus values will for a_{i} will only have to be recomputed after an interval.
a_{n} = x. \left\lfloor\dfrac{a_{n}}{x}\right\rfloor+r
a_{n} = (x-1). \left\lfloor\dfrac{a_{n}}{x}\right\rfloor+\left(r+1.\left\lfloor\dfrac{a_{n}}{x}\right\rfloor\right)
a_{n} = (x-2). \left\lfloor\dfrac{a_{n}}{x}\right\rfloor+\left(r+2.\left\lfloor\dfrac{a_{n}}{x}\right\rfloor\right)
a_{n} = (x-3). \left\lfloor\dfrac{a_{n}}{x}\right\rfloor+\left(r+3.\left\lfloor\dfrac{a_{n}}{x}\right\rfloor\right)
.
.
.
a_{n} = (x-m). \left\lfloor\dfrac{a_{n}}{x}\right\rfloor+\left(r+m.\left\lfloor\dfrac{a_{n}}{x}\right\rfloor\right)
This will be valid until the remainder is less than the divisor,
thus for the next m iterations the value dosent have to be updated.
\therefore x-m\leq r+m.\left\lfloor\dfrac{a_{n}}{x}\right\rfloor
\therefore \dfrac{x-r}{\left\lfloor\dfrac{a_{n}}{x}\right\rfloor +1}\leq m
I used a vector of vectors, where the i^{th} index points to the list of values that are to be updated on the i^{th} iteration. So once u compute m , you can append the index of the person in the (i+m)^{th} position on this array.
[link to my solution][1]
can someone please help me with the time complexity of this method?
[1]: https://www.codechef.com/viewsolution/23572516