ABC327 B問題（A^A）を解く

AtCoder が提供しているABC（AtCoder Beginner Contest）327 のB問題をC++とPythonで解いてみました。ABC327は、2023年11月4日21:00に実施されました。

AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。

B問題 A^A（Difficulty : 129）

問題はリンク先をご覧ください。

ABC327 B問題 A^A

全探索しますが、範囲は狭いです。AtCoder Problems による Difficulty は、129 でした。

解答案

$A^A$ は、速く大きくなります。

$$15^{15} \doteqdot 4.38 \times 10^{17}$$

$$16^{16} \doteqdot 1.84 \times 10^{19}$$

制約から $1 \leqq B \leqq 10^{18}$ であるため、$1 \leqq A \leqq 15$ までの範囲を調べればよいことが分かります。

C++ プログラム例（ABC327B）

$A^A$ を上記の範囲で求めて、$B$ と比較します。

以下が、C＋＋プログラムとなります。

#include <bits/stdc++.h>
using namespace std;

typedef unsigned long long int ull;

int main()
{
	ull b;
	cin >> b;

	int result = -1;
	for (ull i = 1; i <= 15; ++i) {
		ull n = 1;
		for (ull j = 1; j <= i; ++j) {
			n *= i;
		}
		if (n == b) {
			result = i;
			break;
		}
	}

	cout << result << endl;

	return 0;
}

AC（Accepted＝正しいプログラム）と判定されました。

Python プログラム例（ABC327B）

Python では、演算子 ** で累乗が表現できるため簡単に書けます。以下となります。

"""AtCoder Beginner Contest 327 B"""
b = int(input())

result = -1
for i in range(1, 16):
    if i ** i == b:
        result = i
        break

print(result)

こちらも「AC」と判定されました。

最後に

全探索の範囲を探すために、Windows11附属の電卓（calc.exe）を「関数電卓」モードにして計算しました。

引き続き ABC の問題を紹介していきます。