AtCoder ABC 108 C問題 解説補足

Triangular Relationship

C - Triangular Relationship

n以下の整数の組(a, b, c)において、 a + b, b + c, c + a が全てkの倍数であるものの個数を求めよ。

解説

$${a + b = kx}$$, $${b + c = ky}$$, $${c + z = kz}$$ とおくと、

$$
\begin{align*}
2a &= k(x - y + z) \\
&= kw
\end{align*}
$$

が導かれる。

従って以下のように場合分けすることができる。

1. a, b, c が k の倍数である時

つまり $${a \;\%\; k = b \;\%\; k = c \;\%\; k = 0}$$ である。

2. a, b, c が w の倍数である時

この時は、k は 2 の倍数である。

$$
\frac{a}{w} = \frac{k}{2}
$$

従って、左辺の $${\frac{a}{w}}$$ は整数であるという条件が生まれる。

また w は任意の値であるから、w = 1 から考慮していくと、

• $${w = 1 \Rightarrow a = \frac{k}{2} \quad \therefore\; a \;\%\; k = \frac{k}{2}}$$

• $${w = 2 \Rightarrow \frac{a}{2} = \frac{k}{2} \quad \therefore\; \frac{a}{2} \;\%\; k = \frac{k}{2} \quad \text{where}\; a \;\%\; 2 = 0}$$

• $${w = 3 \Rightarrow \frac{a}{3} = \frac{k}{2} \quad \therefore\; \frac{a}{3} \;\%\; k = \frac{k}{2} \quad \text{where}\; a \;\%\; 3 = 0}$$

• …

故に、 $${w = 1}$$ 以外では、a(,b, c) に条件が付与され、題意の 全てkの倍数 を満たすことが出来ない。

従って題意を満たすには、 $${w = 1}$$ のときに限られ、  x, y, z が全て 1 であることが判明する。

与えられた問題は、

n以下の整数の組(a, b, c)において、 a + b, b + c, c + a が全て kの倍数 であるものの個数を求めよ。

から

n以下の整数の組(a, b, c)において、 a + b, b + c, c + a が全て k であるものの個数を求めよ。

と書き換える事ができる。

ゆえに題意をみたす(a,b,c)の組は

• $${a \;\%\; k = b \;\%\; k = c \;\%\; k = 0}$$

• kが偶数の時は $${ a \;\%\; k = b \;\%\; k  = c \;\%\; k  = \frac{k}{2}}$$ 

という条件が生まれる。