Modularness [AtCoder Beginner Contest 156 F]

https://atcoder.jp/contests/abc156/tasks/abc156_f

解説

https://atcoder.jp/contests/abc156/submissions/10318264

(104) AtCoder Beginner Contest 156 - YouTube
解説AC。
これを思いつくのは厳しい。かなり賢い考え方。
けれど、見たことのあるテクはいくつかある。

• 与えられた条件の逆なら数えやすい
• 与えられた要素をすべてmod Mにとりあえずする
• 【NEW!】d<Mであるとき、a+d>b+d (mod M)となるのは、(a+d)/Mの商<(b+d)/Mの商のとき

数列の末項の計算の仕方を紹介しておく。
数列がN項であるということは、末項は数列dをN-1回足したものであるため、Nは-1しておこう。
d全体の総和をtotとしておく。
N/Kの商を考えると、これがd全体を足す回数となる。
よって、これを先に足す。end += 1LL * (N / K) * tot;
すると、残りの回数はN%K回となるので、それだけ愚直に足す。
rep(i, 0, (N%K)) end += DD[i];
これでO(K)で用意できるので間に合う。

int K, Q, D[5010];
int DD[5010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> K >> Q;
    rep(i, 0, K) cin >> D[i];
    rep(_, 0, Q) {
        int N, X, M; cin >> N >> X >> M;

        rep(k, 0, K) {
            DD[k] = D[k] % M;
            if (DD[k] == 0) DD[k] = M;
        }
        X %= M;

        ll tot = 0;
        rep(k, 0, K) tot += DD[k];
        
        ll start = X;
        ll end = X;

        N--;
        end += 1LL * (N / K) * tot;
        rep(i, 0, (N%K)) end += DD[i];

        ll ng = end / M - start / M;
        ll ans = N - ng;
        printf("%lld\n", ans);
    }
}