AtCoder ABC 378 B - Garbage Collection (5Q, 灰色, 200 点)

演算子「%」を上手に使う系の数学問題。

• 問題へのリンク

問題概要

種類のゴミがある。ゴミ は、 で割って 余る日に捨てることができる。

次の 個のクエリに答えよ。

【クエリ】
ゴミ を、 日目以降に捨てたい。最短で捨てることのできる日を答えよ。

制約

• 

考えたこと

見た目はクエリ処理の問題だけど、結局は次の問題が解ければよい。

---

で割って 余る整数のうち、 以上の最小の整数を求める

---

これは、実は過去に「まんま」の記事を書いた。

drken1215.hatenablog.com

ここに書いた方法を使えば、 の計算量で解ける。

コード

#include <bits/stdc++.h>
using namespace std;

// m で割って r 余る x 以上の最小の整数
long long amari_lower_bound(long long x, long long m, long long r) {
    x -= r;
    long long rx = (x % m + m) % m;
    return (rx > 0 ? x + (m - rx) + r : x + r);
}

int main() {
    int N, Q;
    cin >> N;
    vector<long long> q(N), r(N);
    for (int i = 0; i < N; i++) cin >> q[i] >> r[i];

    cin >> Q;
    while (Q--) {
        int t, d;
        cin >> t >> d;
        t--;

        cout << amari_lower_bound(d, q[t], r[t]) << endl;
    }
}