Triangular Relationship [AtCoder Beginner Contest 108 C]
私にとってはかなり難しい問題でした。よって、何段階かに分けて理解します。
剰余の式を理解する
まず、以下の式変形を見てください。
・(a+b) % K = (a+c) % K
・b % K = c % K
以前も何かの問題で見た気がしますね。a=5, b=4, c=8, k=4 のときの、この式変形を、図で表してみます。
・aaaa/abbb/b
・aaaa/accc/cccc/c
つまり、K で割ったときの余りが等しいという事実は、左右の共通部分である a ではなく、左右で異なっている部分である b,c にのみ依存する、よって、両辺から a を引いても余りが等しいという事実は変わらない、という意味なんでしょう。
数学的に論理的に、ではなく、直感的に感覚的にしか理解できていませんが、とりあえず先に進みます。
a,b,c のうちの1つがKの倍数であるとき
a+b, b+c, a+c が全て K の倍数になるような a,b,c とは、いったいどのようなものなんでしょうか。
a,b,c のいずれかがもともと K の倍数であった場合を考えてみます。仮に a だとすると、a%K=0 です。
a%K=0 となるような a に足し合わせて K の倍数となるような b を考えます。このとき、b も同様に b%K=0 で、K の倍数である必要があります。6 に足して 6の倍数 になるような数は、やはり 6 の倍数以外にはないんですね。同様に、c も c%K=0 である必要があります。
となれば、条件を満たす a,b,c の組み合わせとして、
・a%K = b%K = c%K = 0
となる a,b,c が考えられます。
このような a,b,c のうち、a の個数は「1～N のうち K で割った余りが 0 になる数」の個数です。
これを仮に x とします。a,b,c は重複してもよいので、このような a,b,c の組み合わせの個数は x^3 となります。
a,b,c のうちの1つがKの倍数でないとき
仮に、a+b が 6 の倍数になるような a, b の組み合わせのうち、a も b も 6 の倍数でない場合を考えてみます。
以下のようなものが考えられます。
・1, 5
・2, 4
・3, 3
これを一般化すると、a%6 + b%6 = 6 となるような a,b だけが、a+b が 6 になり得ることがわかります。
では、これを今回の問題に当てはめてみます。
a,b,c の組み合わせは、a+b, b+c, a+c が全て K の倍数でなければいけません。すなわち、
・(a+b)%K=0 && (b+c)%K=0 && (a+c)%K=0
です。これを冒頭に紹介した式変形であれやこれやすると、
・a%K = b%K = c%K（式1）
が求まります。さらに、先ほど 6 の倍数を例に挙げて説明した a%6 + b%6 = 6 を使って、
・a%K + b%K = K
・b%K + c%K = K
・a%K + c%K = K（式2）
が得られます。式1と式2で連立方程式を立てて計算すると、
・a%K = b%K = c%K = K/2
が求まります。ここまでくればあと一息です。
a の個数は「1～N のうち K で割った余りが K/2 になる数」の個数です。これを仮に y とします。
a,b,c は重複してもよいので、このような a,b,c の組み合わせの個数は y^3 となります。
ただし y は K/2 が整数、すなわち K が偶数のとき以外は 0 となるので、注意が必要です。
最後に、前の章で求めた x^3と y^3 を足して、答えになります。
void solve () { int n = nextInt(), k = nextInt(); long ans = 0L; //xを求める long x = 0; for (int i=1; i<=n; i++) { if (i%k == 0) x++; } //yを求める long y = 0; if (k%2 == 0) { for (int i=1; i<=n; i++) { if (i%k == k/2) y++; } } out.println(x*x*x + y*y*y); }
これだけ解説を書いて、一応は理解できましたけど……この問題がもし本番で出題されていたら、間違いなく解けなかったでしょうね。
