問題
lo から hi までのすべての a と b について a^b を計算します。2^4 = 4^2 = 16 のように、同じ値になるものもあります。異なる値が何個あるかを数えてください。値そのものは非常に大きくなりますが、実際に計算する必要はありません。a を r^k(r はそれ自身が累乗数でない数)と表すと、a^b = r^(k × b) です。2つのべき乗が等しいのは、r が同じで、指数 k × b も同じときに限ります。
distinct_powers(lo, hi) を実装してください。
入力
lo:底と指数の最小値。
hi:底と指数の最大値。
出力
lo ≤ a ≤ hi、lo ≤ b ≤ hi を満たす a^b の異なる値の個数を返してください。
制約
2 ≤ lo ≤ hi ≤ 100
例
入力:
lo = 2
hi = 4
期待される出力:
expected = 8
入力:
long long lo = 2;
long long hi = 4;
期待される出力:
long long expected = 8;
入力:
long lo = 2;
long hi = 4;
期待される出力:
long expected = 8;
解説
9個のべき乗は 4, 8, 16, 9, 27, 81, 16, 64, 256 です。16 が2回現れるので、異なる値は 8 個です。
入力:
lo = 7
hi = 7
期待される出力:
expected = 1
入力:
long long lo = 7;
long long hi = 7;
期待される出力:
long long expected = 1;
入力:
long lo = 7;
long hi = 7;
期待される出力:
long expected = 1;
解説
7^7 だけなので 1 です。
解き方のヒント
まずは自分で考えてから、ヒントを 1 つずつ開いてみましょう。
ヒント 1
r^k = a となる最小の r と最大の k を求めます。
ヒント 2
a^b は r^(k × b) に等しいので、組 (r, k × b) で値を特定できます。
ヒント 3
その組を集合に入れて、個数を数えます。
目安の計算量
時間 O((hi − lo)² log hi)、追加メモリ O((hi − lo)²)
参考資料
この課題はCodeUtility用に調整されています。上記の説明と制約に従ってください。