私はこの1つに遭遇したとき、私は最近、問題を解決して異なる拠点

Question

で数表現を見つける：APAC Round E Q2

基本的に質問が最小のベースを見つけることが求められます（> 1）の数（入力）が、その後書かれている場合せますその数は1だけで構成されます。基底2で表現されている場合は3になります（1のみで構成されます）。

今、私はこのようなベースを見つけるために2から数までのすべての基底を試しています。しかし、この制約にはより効率的なものが必要でした。

誰でもこの方法に手助けをすることはできますか？ここで

Answer 1

私たちは順番に最高の電力達成可能で最小のベース、2、および幾何学的合計の計算式を使用して対応するであろうことを認識することによってO((log2 n)^2)複雑でこれを解決することができます。

1 + r + r^2 + r^3 ... + r^(n-1) = (1 - r^n)/(1 - r) 

Renaming the variables, we get: 

    n = (1 - base^power)/(1 - base) 

は、今、私たちは唯一のに必要powerを(floor(log2 n) + 1)から2までチェックしてください。それぞれの所与の累乗について、ベースのバイナリ検索を使用してください。たとえば：

10^18周り nについては

n = 13: 

    p = floor(log2 13) + 1 = 4: 

    Binary search for base: 

    (1 - 13^4)/(1 - 13) = 2380 

    ... 

    No match for power = 4. 

    Try power = 3: 

    (1 - 13^3)/(1 - 13) = 183 

    (1 - 6^3)/(1 - 6) = 43 

    (1 - 3^3)/(1 - 3) = 13 # match 

我々は最大(floor(log2 (10^18)) + 1)^2 = 3600回の反復が必要な場合があります。

Answer 2

は1つの提案です：あなたはbによって数値divisbleで終わるこの番号から1を引く場合はベースb内のすべての1のように表すことができる数xはx = b^n + b^(n-1) + b^(n-2) + ... + b^1 + 1

のように書くことができます。 b^n + b^(n-1) + b^(n-2) + ... + b^1であり、これは111...110という表現を有する。 bで割り算すると、右に1回シフトすることを意味します。結果の数値は、b^(n-1) + b^(n-2) + ... + b^1または111...111になります。今度は、0に達するまでプロセスを繰り返すことができます。ベース3で111ある例13については

：

13 - 1 = 12 --> 110 
12/3 = 4 --> 11 
4 - 1 = 3 --> 10 
3/3 = 1 --> 1 
1 - 1 = 0 --> 0 
Done => 13 can be represented as all 1s in base 3 

その数はによってdivisbleであれば与えられた数は、ベースb内のすべての1秒で書き込むことができるかどうかを確認するために、あなたは確認することができますbを引いた後に1となります。そうでない場合は、すぐに次のベースから開始することができます。

これは非常に簡単ですが、繰り返しごとに基本変換、1つの減算、1つの除算、1つのmod演算を実行しません。