AtCoder が提供しているABC（AtCoder Beginner Contest）297 のD問題をC++とPythonで解いてみました。ABC297は、2023年4月9日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
D問題 Count Subtractions（Difficulty : 273）
問題はリンク先をご覧ください。
引き算を掛け算に置き換えて計算します。AtCoder Problems による Difficulty は 273 でした。
解答案
問題を書いてある手順をそのままプログラムすると以下となります。
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long int ull;
int main()
{
ull a, b;
cin >> a >> b;
ull result = 0;
while (a != b) {
if (a > b) {
a = a - b;
} else if (a < b) {
b = b - a;
}
++result;
}
cout << result << endl;
return 0;
}このプログラムは、$A$ と $B$ の差が大きい場合は、多くの回数の引き算が発生します。また、$ 1 \leqq A, B \leqq 10^{18}$ と $A, B$ が大きいため、単純なこのプログラムでは、TLE（Time Limit Exceeded）判定となります。
C++ プログラム例（ABC297D）
一回一回引くのではなく、引ける数の回数を計算して掛け算をして引きます。
$A < B$ の場合は、$A$ と $B$ を入れ替えて $A > B$ とします。$A = 8, B = 3$（入力例1）は、以下のように推移（$B$ を引く）します。
$$(8, 3) \to (5, 3) \to (2, 3)$$
上記の場合、$8 – 3 = 5$ に対して、$3$ を $2$ 回引いています。別の例として $A = 9, B = 3$ は、以下のように推移します。
$$(9, 3) \to (6, 3) \to (3, 3)$$
この場合は $2$ 回引いて、$A = B$ となり終了します。
まとめると、以下となります。
- $(A – B)$ が $B$ で割り切れない場合、$(A – B) / B + 1$ 回操作（$B$ を引く）を繰り返す。
- $(A – B)$ が $B$ で割り切れる場合、$(A – B) / B$ 回操作（$B$ を引く）を繰り返す。 そして $A = B$ となり操作を終了する。
操作回数を変数 result に加えて、最後に result を出力します。以下がC++プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long int ull;
int main()
{
ull a, b;
cin >> a >> b;
ull result = 0;
ull temp;
while (a != b) {
if (a < b) {
swap(a, b);
}
if ((a - b) % b == 0) {
temp = (a - b) / b;
} else {
temp = (a - b) / b + 1;
}
a -= temp * b;
result += temp;
}
cout << result << endl;
return 0;
}上のプログラムでは、$M / N$ を切り上げた値を求めています。この値は、一般的に
$$(M + N – 1) / N$$
で求めることができます。この問題の場合
$$((A – B) + (B – 1))/ B = (A – 1) / B$$
となります。この演算で if 文を減らすことができます（17行目）。
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long int ull;
int main()
{
ull a, b;
cin >> a >> b;
ull result = 0;
ull temp;
while (a != b) {
if (a < b) {
swap(a, b);
}
temp = (a - 1) / b;
a -= temp * b;
result += temp;
}
cout << result << endl;
return 0;
}どちらも AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC297D）
C++ の後者のプログラムを Python に移植しました。
"""AtCoder Beginner Contest 297 D"""
a, b = map(int, input().split())
result = 0
while a != b:
if a < b:
a, b = b, a
temp = (a - 1) // b
a -= temp * b
result += temp
print(result)こちらも「AC」と判定されました。
最後に
この問題は、引き算の回数を問題にしていますが、結果的にユークリッドの互除法で最大公約数を求めています。$A = B$ となった値は、元の $A$ と $B$ の最大公約数になっています。
引き続き ABC の問題を紹介していきます。
