AtCoder BC108 C: Triangular Relationship

問題

C - Triangular Relationship
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

解法

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

コメント

タイトルとURLをコピーしました