AtCoder が提供しているABC（AtCoder Beginner Contest）324 のB問題をC++とPythonで解いてみました。ABC324は、2023年10月14日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
B問題 3-smooth Numbers（Difficulty : 91）
問題はリンク先をご覧ください。
与えられた数を2と3で割れるだけ割ります。AtCoder Problems による Difficulty は、91 でした。
解答案
与えられた $N$ が、$2^x 3^y$ の形になっているか判定します。問題は、以下のように読み替えることができます。
$N$ を、2で割り切れるだけ割る。次に3で割り切れるだけ割る。その結果が1になるか？
もし、$N$ が2と3以外の素因数を含んでいるなら、その素因数を含んだ数が結果として残り1となりません。また、結果が1なら、割る操作の逆を考えると $2^x 3^y$ の形として表すことができます。
C++ プログラム例（ABC324B）
$1 \leqq N \leqq 10^{18}$ と大きいですが、$10^{18} \doteqdot 2^{60}$ なので、割る操作は多くとも60回程度となります。また、32ビット整数には収まらないため、64ビット整数（unsigned long long）を使いました。
以下が、C＋＋プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long int ull;
int main()
{
ull n;
cin >> n;
while (n % 2 == 0) {
n /= 2;
}
while (n % 3 == 0) {
n /= 3;
}
if (n == 1) {
cout << "Yes" << endl;
} else {
cout << "No" << endl;
}
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC324B）
基本的な考え方は同じです。Python では、整数の大きさに気をつける必要はなく、少し楽です。以下となります。
"""AtCoder Beginner Contest 324 B"""
n = int(input())
while n % 2 == 0:
n //= 2
while n % 3 == 0:
n //= 3
print("Yes" if n == 1 else "No")こちらも「AC」と判定されました。
最後に
問題は、数式で提示されていますが、プログラムの操作として読み替えることがポイントでした。
引き続き ABC の問題を紹介していきます。
