You will be given an array, $A$ of length $n$ and $q$ queries. In each query you will be given a value $x$. You have to perform $A_{i} = A_{i} \text{ (mod $x$)} , 1 \le i \le n$ for each query , and after all the query print the array.

Constraints

Solution:⌗

When $A_{i} = A_{i} \text{ (mod $x$)}$ operation change $A_{i}$ ?

Answer

Lets call a $A_{i}$ valid, for a given $x$, if $A_{i}\ge x$.

Hence, our solution is, for each query, we will iterate over only valid numbers, and do %= operation on them [a%=x].

Inside Math:⌗

But why this solution will work?

Suppose, $a$ is valid for $x$, and we have done $a'=a \text{ (mod $x$)}$.

Now, $a'\le \frac{a}{2}$ [But why ?]

  • Case 1: $x\le \frac{a}{2}$

    • Hence, if we divide $a$ with $x$, the remainder will be smaller than $x$.

    • $\therefore$ $a'\le x$ or $a'\le \frac{a}{2}$

  • Case 2: $x>\frac{a}{2}$

    • Hence the remainder will be $a-x$.

    • $\therefore a'=a-x$ or $a'\le\frac{a}{2}$

Hence, one value, $A_{i}$, will become a valid value atmost $log_{2}{(2^{60})} = 60$ times.

Hence if we iterate over only the valid value , number of overall iteration will be amortize $60\times n$.

But as we are using priority_queue to maintain our array our total complexity will be $O(nlog(n)log(A_{max}))$

Reference:⌗