アマリクエリ [yukicoder 885]

https://yukicoder.me/problems/no/885

解説

https://yukicoder.me/submissions/379434

剰余にまつわる重要な性質がある。
1度剰余が行われると、値が変わらないか、半分未満の数に変わる。
よって、各要素について値が変わる回数はlogA[i]回となる。
つまり、毎回のクエリで値が変わるものだけ変えていけば、ならしNlogAとなり間に合う。
どの数で値が変わるかは数が大きいものから順番に見ていけばいい。
大きいものから見ていったときに値が変わらないなら、それ以降も値は変わらない。
剰余を取るときに、総和からその数を引き、剰余をとったあとの数を足せば差分計算が可能。

int N, A[101010], Q;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    priority_queue<int> que;
    ll tot = 0;
    rep(i, 0, N)
    {
        cin >> A[i];
        que.push(A[i]);
        tot += A[i];
    }
    cin >> Q;
    rep(q, 0, Q) {
        int x; cin >> x;
        while(x <= que.top()) {
            int qu = que.top();
            que.pop();
            tot -= qu;
            qu %= x;
            tot += qu;
            que.push(qu);
        }
        printf("%lld\n", tot);
    }
}