ガジェット通信

見たことのないものを見に行こう

数学の問題をプログラミングで解こう!「ロング・ロング・ストリング」問題解説

DATE:
  • ガジェット通信を≫

問題のおさらい

自然数 n に対して、関数 F(n) を、nn(n の n 乗)を 10 進数で表したときの桁数と定義します。
例えば、55 = 3125 ですので、F(5) = 4 です。同様に、F(20) = 27 です。

さらに、2 以上の自然数 m に対して、F(n) = m となる n の値を G(m) と定義します。
もしそのような n が存在しない場合は、G(m) = -1 と定義します。

例えば G(4) = 5、G(27) = 20 です。同様に、G(7) = -1、G(101) = 57、G(11111) = 3173 となることが確かめられます。

標準入力から、自然数 m(2 ≦ m ≦ 1010)が与えられます。
標準出力に G(m) の値を出力するプログラムを書いてください。

方針

非常に長い桁数の数字に関する問題です。

まず、n の n 乗の値そのものを計算するアプローチがうまくいかないことは、多くの方が気づかれたのではと思います。本問で扱う数は、桁数が最大で 1010 桁もある巨大な数です。通常のプログラミング言語の数値型の変数では、精度が不十分だったり、莫大なメモリ量を要したりして、うまく扱うことができません。

そこで役に立つのは、常用対数 の考え方です。常用対数とは、10 を底とする対数(log)のことです。巨大な数のおおよその値を表すための概念で、まさに今回のケースにうってつけです。

さらに、常用対数には、10進数の桁数との深い関連性があります。自然数 x に対して log x の整数部分に 1 を足すと、x の桁数に等しくなるのです。

参考:常用対数(Wikipedia)

したがって、n に対する n の n 乗の桁数は、次のコードで求められます。

// nのn乗の桁数
long long NumOfDigitsOfNToTheN(long long n) {
return 1 + (long long)(n * log10((double)n));
}

さて、この関数を使って、この値が m に等しくなるような n を探索するコードを書けばよさそうです。しかし、n を 1 から始めて 1 ずつ増やしていく次のようなコードはうまくいきません。m の上限が 1010 もあり、頭から探索する方法では時間がかかり過ぎてしまうためです。

// 時間がかかり過ぎてしまうコード
#include
#include
using namespace std;

long long NumOfDigitsOfNToTheN(long long n) {
return 1 + (long long)(n * log10((double)n));
}

int main() {
long long m = 100, d;
cin >> m;
for (long long n = 1;; n++) {
d = NumOfDigitsOfNToTheN(n);
if (d == m) { // 発見!
cout

カテゴリー : デジタル・IT タグ :
CodeIQ MAGAZINEの記事一覧をみる ▶
  • 誤字を発見した方はこちらからご連絡ください。
  • ガジェット通信編集部への情報提供はこちらから
  • 記事内の筆者見解は明示のない限りガジェット通信を代表するものではありません。