Triangular Relationship [AtCoder Regular Contest 102 C]

https://beta.atcoder.jp/contests/arc102/tasks/arc102_a

解法

https://beta.atcoder.jp/contests/arc102/submissions/3127393

(a+b) % K = 0
(a+c) % K = 0
これを言い換えると
(a+b) % K = (a+c) % K
b % K = c % K
となる。
他の組合せでもやると、a%K = b%K = c%Kが成り立つとわかる。
それに加えて (a+b)%K=0になるためには、a%K=b%K=c%K=0かa%K=b%K=c%K=K/2のどちらかである。
　
まず、a%K=b%K=c%K=0のパターンを数えよう。
[1,N]の中でmodKが0になる個数をm0とする。
すると(a,b,c)の組み合わせ数はm0^3となる。
　
次に、a%K=b%K=c%K=K/2のパターンであるが、これはKが偶数の場合しか数えない。
[1,N]の中でmodKがK/2となる個数をcとする。
すると同様に(a,b,c)の組み合わせ数はc^3となる。

int N, K;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> K;
 
    ll ans = 0;
 
    int m0 = 0;
    rep(i, 1, N + 1) if (i % K == 0) m0++;
    ans = 1LL * m0 * m0 * m0;
 
    if (K % 2 == 0) {
        int c = 0;
        rep(i, 1, N + 1) if (i % K == K / 2) c++;
        ans += 1LL * c * c * c;
    }
    cout << ans << endl;
}