Здравствуйте! Помогите, пожалуйста, решить следующую задачу: 736. Удаление с acmp.ru. Суть задачи: на каждой итерации из массива длины n до 5·10⁶ удаляются элементы с индексами k, 2k, 3k и т.д. Затем все неудаленные элементы сдвигаются и операция повторяется до тех пор, пока длина массива не станет меньше k. Нужно для каждого элемента во вводе сообщить, каким по счету он уйдет.

Мое решение — явная обработка каждого запроса:

#include <stdio.h>
 
inline int solve(int n, int k, int a) {
    int answ = 0;
    while (a >= k && a % k != 0) {
        answ += (n - answ) / k;
        a -= a / k;
    }
    answ += a / k;
    return answ;
}
 
int main() {
    int n, k, q;
    scanf("%d %d %d", &n, &k, &q);
     
    while (q--) {
        int item;
        scanf("%d", &item);
        printf("%d\n", solve(n, k, item));
    }
     
    return 0;
}

Решение получает TLE, видимо, нужно как-то сгруппировать запросы, а то, скорее всего, при таком наивном подходе сложность получается порядка O(q*n). До этого предпринималась попытка для каждого элемента предподсчитать ответ, что также дало TLE.

Была идея с деревом Фенвика за O(n log(n)^2), но она не пройдет по времени.