ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

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}がこのパターンの個数となります。
最後に上限のパターンの和を求めれば、答えが求まります。