AtCoderログ：0051 - ABC 156 B

問題

問題文

整数 $N$ を $K$ 進数で表したとき、何桁になるかを求めてください。

制約

・入力は全て整数である。
・$1 \le N \le 10^9$
・$2 \le K \le 10$

収録されている問題セット

• AtCoder に登録したら次にやること (第05問類題)

回答

回答1 (AC)

例えば $1234$ という整数は $1 \times 1000 + 2 \times 100 + 3 \times 10 + 4$ (1つの1000と2つの100と3つの10と4の和) という構造になっています。ここで$1000,100,10$ はすべて $10$ のべき乗 ($1000=10^3$, $100=10^2$, $10=10^1$) に由来しているため、このような整数の表し方を10進法と呼びます。今回は $K$ 進法表記の問題なので、$10$ のべき乗の代わりに $K$ のべき乗を使用します。

再び n=1234 の例で k=10 のときに各桁の求め方を考えてみましょう。最下位の 4 は n%10 で求められます。10 の位の 3 は n/10 の最下位なので、(n/10)%10 で求められますが、別の見方をすると、(最下位の 4 を求めた後に) n を n/10 で置き換えた上で n%10 で求めることもできます。同様に、さらに n を n/10 で置き換えた上で n%10 を求めると 100 の位 2 が得られます。最後に、さらに n を n/10 で置き換えた上で n%10 を求めると 1000 の位 1 が得られます。最後に n を n/10 で置き換えると値は 0 になるので、全ての桁が計算できたことがわかります (下表参照)

n の値	n%10	n/10
1234	4	123
123	3	12
12	2	1
1	1	0

処理手順としては、$K$ 進法で表記した値を保持するための文字列 s (最初はヌル)を用意します。$K$ 進法における最下位の値は n%k となるので、この値を文字列として s に保存し、n を n%k で置き換えます。この処理を n が 0 になるまで繰り返します。n が 0 になると、文字列 s に $K$ 進法表記が完成しているので、その桁数 s.size() を出力して終了となります。コードは以下のようになりました。

abc156b-1.cpp

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

int main() {
  int n, k;
  cin >> n >> k;

  string s = "";
  while ( n>0 ) {
    s += to_string(n%k);
    n =  n/k;
  }
  
  cout << s.size() << endl;
}

回答2 (AC)

問題では $N$ を $K$ 進法で表した時の桁数を聞かれているので、$K$ 進数での表現は必要ありません。そこで桁数を直接計算してみましょう。

例えば $10$ 進法で $2$ 桁の整数は $10$ 以上 $99$ 以下ですが、これは $10^1$ 以上 $10^2-1$ 以下と表すことが出来ます。同様に、$10$ 進法で $m$ 桁の整数 $x$ は $10^{m-1} \le x \le 10^m-1$ となります。ここで両辺の対数をとると $\log_{10}{10^{m-1}} \le \log_{10}{x} \le \log_{10}{(10^m-1)} < \log_{10}{10^m}$ となり $m-1 \le \log_{10}{x} < m$ が得られます。この式が言っているのは「$m$ 桁の整数 $x$ の対数値は $m-1$ 以上 $m$ 未満である」ということです。従って、整数 $x$ の(底が $10$ の)対数値の小数点以下を切り捨てれば $m-1$ が得られる、つまり「整数 $x$ の桁数は $\lfloor \log_{10}{x} \rfloor +1$ 桁である」ことがわかります (ここで $\lfloor a \rfloor$ は $a$ の小数点以下を切り捨てる関数)。

問題は整数 $N$ を $K$ 進数で表した時の桁数を聞いているので、$10$ 進数と同じように考えて、桁数は $\lfloor \log_{k}{x} \rfloor +1$ となります。通常、$\log_k$ という関数は用意されていませんが、対数関数の性質より、$\log_{k}{x}=\log_{10}{n}/\log_{10}{k}$ となるので、簡単に計算可能です。コードは以下のようになりました。

abc156b-2.cpp

#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int n, k;
  cin >> n >> k;

  int ndigit = int(log(n)/log(k))+1;

  cout << ndigit << endl;
}

調べたこと

AtCoder の解説 → ユーザ解説

k で割り切れる回数から桁数を求めていました。

AtCoder の解説 → コンテスト全体の解説

こちらも k で割り切れる回数から桁数を求めていました。

リンク

前後の記事

• 前の記事 → AtCoderログ：0050 - ABC 212 A
• 次の記事 → AtCoderログ：0052 - ABC 212 B