AtCoder ABC 108 C問題 解説補足
Triangular Relationship
n以下の整数の組(a, b, c)において、 a + b, b + c, c + a が全てkの倍数であるものの個数を求めよ。
解説
$${a + b = kx}$$, $${b + c = ky}$$, $${c + a = 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}}$$
という条件が生まれる。