AtCoder Beginner Contest 108 - C Triangular Relationship

これ本当に300点ですか？？？

概要

N 以下の正の整数の組(a, b, c)であって、a+b, b+c, c+a が全てKの倍数であるようなものの個数を求める。

考察

1

%を剰余演算の記号とする。

制約が N <= 2*10⁵なので、aだけを全探索するような実装が予想される。 なので、aを定数と見立てて、b,cのパターンの数を求めるような実装がしたい。

まず、b+cがKの倍数であるようなものについて考察する。 bをx軸、cをy軸に取って、b+cがKの倍数となるような点をマークしていくと、斜めの直線が複数現れると思う。

ここにaの制約を入れたい。a+bがKの倍数なので、bをKで割った余りは(K-a)%K*1でなければならない。 cも同様。

b%K=(K-a)%K となる直線たちと c%K=(K-a)%K となる直線たちを引く。3つの直線が交わる点の個数が、aを固定したときのb,cの個数となる。

実装

int main() {
    int N, K;
    scanner >> N >> K;
    ll ans = 0;
    
    iterate(a, 1, N+1) {
        const int x = K - a%K;
        if ((x + x)%K != 0) continue;
        const ll n = (N - x)/K + 1;
        ans += n*n;
    }
    
    printer << ans << '\n';
    return 0;
}

いや確かにシンプルですけど…

*1:0以上K未満とする