C - Triangular Relationship

競プロ

はじめに

競技プログラミング、AtCoder Beginner Contest 108
C - Triangular Relationship
言語はC#
何かあればTwitter→@pirorirori_n712まで

問題

問題文

整数 N,Kが与えられます。
N以下の正の整数の組 (a,b,c)であって、a+b,b+c,c+aがすべて Kの倍数であるようなものの個数を求めてください。 
ただし、a,b,cの順番を入れ替えただけの組も異なるものとして数えます。
また、a,b,cの中に同じものがあっても構いません。

制約

・1≤N,K≤2×10^5
・N,Kは整数である

入力

入力は以下の形式で標準入力から与えられる。

N K

出力

N以下の正の整数の組 (a,b,c)であって、a+b,b+c,c+aがすべてKの倍数であるようなものの個数を出力せよ。

解き方

以下の記事がとても分かり易いです。
pyteyon.hatenablog.com
qiita.com

上の記事が分かり易いので、
ここでは流れを見るだけにとどめます。
解き方の詳しい内容はありません。

備忘録

以下のコードを参考にしています。
atcoder.jp

この問題を解くうえで重要なことは、modの使用です。
問題文の「Kの倍数」という部分に反応してmodの使用を疑います。

次に、
「N以下の正の整数の組 (a,b,c)であって、a+b,b+c,c+aがすべて Kの倍数であるようなもの」
の個数を最終的に答えなければいけないので
どんなものが(a,b,c)の組になり得るかを考えます。

(a,b,c)では考えにくいので、
初めに(a,b)で考えてみます。

ここで、
modの考え方を適用し

・aとbがどちらもKの倍数であること
・Kが偶数であるとき、aとbがa%K=K/2かつb%K=K/2

であることに気づきます。

これは(a,b)が(a,b,c)になってもそのまま適用できるので
このまま実装にうつります。

先ほど、考えた条件のうち

・aとbとcが全てKの倍数であること

はK偶数、奇数どちらでも使えるのでまずこれを入れます。
N以下のKの個数を数えたいので

N以下のKの倍数=N/K;

で出します。

また、出した個数の組み合わせは
当てはめる場所が(a,b,c)と三か所あり
問題文より数の重複が許されるので

aとbとcが全てKの倍数であるときの(a,b,c)の組の数
=(long)Math.Pow(count, 3);

となります。

longへのキャストはoverflow防止です。

次に以下の条件を考えます。

Kが偶数であるとき、aとbがa%K=K/2かつb%K=K/2かつc%K=K/2

Kが偶数であるときに適用するので
Kが偶数であるかどうかをまずフィルターします。

        if (K % 2 == 0)
        {
             //処理
        }

次にN以下の整数の中で
Kで割ると余りがK/2になる整数の個数を出します。

Kで割ると余りがK/2になる整数の個数 = (N + (K / 2)) / K;

ここでNに（K/2）を足したものをKで割っていることが
少し混乱するので入力例1で考えてみます。

入力例1

3 2

これをそのまま先ほどの式に入れると以下のようになります。

(N + (K / 2)) / K
=(3 + (2 / 2)) / 2
=4/2
=2

(a,b,c)に入る数はN以下でなければならないはずですが
Kを2で割ったものをNに足したものを
Kで割り、個数を出しています。

4以下の2の倍数は
2と4なので4はNである3を超えてしまいますが
Kを2で割ったときに（K/2）の余りがある数が欲しいので
実際には
2と4ではなく、それぞれから（2/1）を引いた
1と3のことを数えています。

そして、ここでも
出した個数の組み合わせは
当てはめる場所が(a,b,c)と三か所あり
問題文より数の重複が許されるので

Kで割ると余りがK/2になる整数の(a,b,c)の組の数
=(long)Math.Pow(count, 3);


偶数の場合は両方の条件の組の数を足した数、
奇数の場合は初めの条件に当てはまる組の数を出力します。

全体のコード

using System;
using System.Linq;
using System.Collections.Generic;

class Cmondai
{
    static void Main()
    {
        var nk = Console.ReadLine().Split(' ').Select(x => Int64.Parse(x)).ToArray();
        var N = nk[0];
        var K = nk[1];
        var ans = 0L;
        //aとbとcが全てKの倍数である
        var count = N / K;
        ans += (long)Math.Pow(count, 3);
        //Kが偶数であるとき、aとbがa%K=K/2かつb%K=K/2かつc%K=K/2
        if (K % 2 == 0)
        {
            count = (N + (K / 2)) / K;
            ans += (long)Math.Pow(count, 3);
        }
        Console.WriteLine(ans);
    }
}