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;
}このプログラムは、
C++ プログラム例（ABC297D）
一回一回引くのではなく、引ける数の回数を計算して掛け算をして引きます。
上記の場合、
この場合は
まとめると、以下となります。
操作回数を変数 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;
}上のプログラムでは、
で求めることができます。この問題の場合
となります。この演算で 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」と判定されました。
最後に
この問題は、引き算の回数を問題にしていますが、結果的にユークリッドの互除法で最大公約数を求めています。
引き続き ABC の問題を紹介していきます。
