AtCoder BC108 C: Triangular Relationship - 銀の弾丸を探して

[mathjax]

a+b、b+c、c+aが全てkで割り切れると言うことは、

$$(a+b)\%k=(b+c)\%k=(c+a)\%k=0$$

ということです。

ここで、aに着目した場合、以下の2通りが考えられます・

・aがkで割り切れる場合　(a+b)%k=0よりbもkで割り切れることになり、さらにcもkで割り切れることになります。　つまり、a、b、cが全てkで割り切れる場合に条件を満たすことになります。

・aがkで割り切れない場合　例えばa%k=1の場合、b%k=k-1となり、c%k=1となります。　その場合、(c+a)%k=0となるにはkが2である必要があります。

　次にa%k=2の場合、b%k=k-2となり、c%k=2となります。　その場合、(c+a)%k=0となるにはkが4である必要があります。

　つまり、kが偶数の場合は、a%k=b%k=c%k=k/2 の場合に条件を満たすことが分かります。

よって、aが偶数の場合と奇数の場合でそれぞれ個数が変わります。

n,k=gets.chomp.split.map(&:to_i)
puts k%2==0 ? (n/k)**3 + ((n-k/2)/k+1)**3 : (n/k)**3