ARC102 C - Triangular Relationship - ツバサの備忘録

ARC初参加でした。

C - Triangular Relationship

提出コード
ガッチガチの考察系ですね。
条件を満たすa,b,cの作り方として、ぱっと思いつくのが、

a,b,cのすべてが $k$ の倍数である

というパターンです。
$k$ の倍数の個数は、 $n/k$ (切り捨て)で求めることができ、a,b,cそれぞれ何を選んでもいいので、 $(n/k)^{3}$ がこのパターンの求める個数になります。
これである程度はクリアなのですが、kが偶数のパターンのみ、あと1つ、作れるパターンがあります。それが、

a,b,cのすべて、 $k$ で割ったときの余りが $k/2$ である

というパターンになります。
$k$ で割ったときのあまりが $k/2$ になるような数の個数は、 $(n+k/2)/k$ (切り捨て)で求めることができ、上のパターンと同様に $((n+k/2)/k)^{3}$ がこのパターンの個数となります。
最後に上限のパターンの和を求めれば、答えが求まります。