すべてのチャレンジ
簡単 0件解決済み 正答率0%

異なるべき乗の個数

ある範囲の a と b について、a の b 乗が何通りの値になるかを数えます。

このチャレンジで学べること

  • 底を最小の根に直せる
  • 巨大なべき乗を計算せずに比較できる
  • 集合を使って異なる値の個数を数えられる

問題

原文(英語)を表示

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

例

例 1
入力:
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 個です。

例 2
入力:
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用に調整されています。上記の説明と制約に従ってください。

ランキング

全体ランキング

コーダーごとのいちばん良い合格解答です。速く、メモリが少なく、評価が高い解答ほど上位になります。

まだ合格した解答はありません。解いて 1 位になりましょう。

他の人の解答から学ぶ

コミュニティの解答

まだ公開された解答がありません。この課題を解いて最初の解答を共有しましょう。