ABC108-C：Triangular Relationship

問題

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

N, K が与えられる。N 以下の整数の組 (a, b, c) で a+b, b+c, c+a がすべて K の倍数であるような組の個数を求めよ。

制約

  • 1 \leq N,K \leq 2\times 10^5

考え方

一つの変数を全探索することを考える。a について mod\ K で [1, a) の範囲を全探索する。a が定まると b,c はそれぞれ b \equiv -a\ (mod\ K), c \equiv -a\ (mod\ K) と一意に決まる。そのときに b+c \equiv 0\ (mod\ K) が満たされていれば良い。

あらかじめ [1, N] の範囲に含まれる mod\ K の個数を求めておけば、全探索したときのそれぞれについて O(1) で求めることができるので全体の計算量は O(N) で解が求める。

Submission #3751671 - AtCoder Beginner Contest 108

どこに着目して考察するべきだったか

1 つの変数までは全探索できることを考える。また与えられている条件は mod\ K 上の演算になることから a について mod\ K で考えることに気づく。

何がバグっていたか

得た知見

mod 上で考えるとうまくいくことがある

類題