Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 297 D問題 Count Subtractions

AtCoder ABC ABC297 D問題 400 pts

問題
提出解答
問題の概要
- 制約
解法

問題

提出解答

問題の概要

整数 $A,B$ に対して, 以下の操作を $A=B$ になるまで行う.

$A \gt B$ ならば, $A \gets A-B$
$A \lt B$ ならば, $B \gets B-A$

$A=B$ になるまで何回の操作を要するか (有限回であることが証明できる)?

制約

$1 \leq A,B \leq 10^{18}$

解法

最初に $A,B$ である状態からの操作回数を $\operatorname{calc}(A,B)$ と置くことにする. ここで, $\operatorname{calc}(A,B)=\operatorname{calc}(B,A)$ より, $A \geq B$ であるとしても一般性を失わない.

ここで, $A$ を $A-B$ に置き換えるという操作を何回連続して行うかを考える. これは

$A-(k-1)B \gt B, \quad A-kB \leq B$

を満たす整数 $k$ を求めることになる.

これを満たす整数 $k$ は

$k=\left \lceil \dfrac{A}{B} \right \rceil-1$

である.

このとき, $A$ から $k$ 回 $B$ を引くと,

$0 \lt A-kB \leq B, A-kB \pmod A \pmod{B}$

であるから,

$A-kB=\begin{cases} A \bmod{B} & (B \not \mid A) \\ B & (B \mid A) \end{cases}$

となる.

ここで, 余りの場合について, $A \bmod{B} \leq \dfrac{A}{2}$ が成り立つ. 実際,

$B \leq \dfrac{A}{2}$ ならば, 余りの定義から $A \bmod{B} \lt B \leq \dfrac{A}{2}$ である.
$(A \gt) B \geq \dfrac{A}{2}$ ならば, $A$ を $B$ で割った商は $1$ 確定なので, $A-B \leq \dfrac{A}{2}$ となる.

よって,

$\operatorname{calc}(A,B)=\left(\left \lceil \dfrac{A}{B} \right \rceil-1 \right)+\operatorname{calc}(B, A \bmod{B})$

であり, この計算を $2$ 回行うと, $\operatorname{calc}$ の第 $1$ 引数が半分以下になる.

よって, 計算量は $O(\log \max(A,B))=O(\log A+\log B)$ 時間である.