Sum Difference [AtCoder Beginner Contest 147 F]

https://atcoder.jp/contests/abc147/tasks/abc147_f

解説

https://atcoder.jp/contests/abc147/submissions/8936937

全体の総和は変わらないので、SかTのパターンを考えればよさそう。
Sのパターンを数えることにする。

組み合わせがちょっと多いので、何かを全探索したい。
高橋君が取る要素の個数を全探索しよう。
高橋くんがM個取ったとすると、総和がMX+?Dとなる。
ここで?Dが取る範囲を雑に考えると最小～最大になるんじゃないかなと想像できる。
つまり、0,D,2D,3D,...と小さい方からA個取ったもの～大きい方からA個取ったものが取りうる範囲である。

これで組み合わせが求まりそうだが、かぶっている所を引かないと行けない。
これを高速に求めるのも難しいのだが、総和がMX+?Dの形になっていてDずつ変化する区間なので、
Dで割ってやって区間を管理したくなる。
だが、MXによって、始点が若干異なるので、その所が問題。
これはMX mod Dで別々に区間を管理することにすれば解決する。

あとは、mod Dするので、Dをしっかり場合分けする必要がある。
D=0のときは別途頑張り、D<0のときは、特にD=-D, X=-xとしても問題ないので、それで対応する。

ll N, X, D;
//---------------------------------------------------------------------------------------------------
ll solve() {
    if (D == 0) {
        if (X == 0) return 1;
        return N + 1;
    }
    if (D < 0) {
        D *= -1;
        X *= -1;
    }

    map<int, SectionStructure> m;

    rep(M, 0, N + 1) {
        int offset = (((1LL * X * M) % D) + D) % D;

        ll L = (1LL * X * M) / D + 1LL * (0 + M - 1) * M / 2;
        ll R = (1LL * X * M) / D + 1LL * (N - 1 + N - 1 - M + 1) * M / 2;

        m[offset].add(L, R);
    }

    ll ans = 0;
    fore(p, m) {
        ll pre = -infl;
        fore(section, p.second.buf) {
            if (abs(section.first) == infl) continue;
            if (section.first == pre) ans--;
            ans += section.second - section.first + 1;
            pre = section.second;
        }
    }
    return ans;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> X >> D;
    cout << solve() << endl;
}