実装例もあるよ!10進数の数字をk進数に変換する

今回も競プロネタです。

与えられた数値を\(k\)(\(k\)は整数)進数に変換する必要に迫られることが多々ある。例えば、与えられた数値を10進法と8進法で書いたときに7が含まれていないかとか求めさせられることがある。
忘れんぼさんで毎回毎回何だったけなぁとなって、その度に調べていていい加減めんどくさくなってきたので、
自分の理解を一度アウトプットしておいて理解の定着を図ることにした。
未来の自分と、このブログにたまたまたどり着いた幸運な(?)読者の方に参考になれば幸いです。

また、競プロ関連の記事は他にも書いています。今後必要なことを拡充していきたいと思いますので参考にしてみて下さい！
→「プログラミングコンテスト」一覧

おさらい~\(k\)進法表記
\(k\)進法表記に変換するときの考え方
実装例
まとめ

おさらい~\(k\)進法表記

まず、\(k\)進法での表記についておさらいする。
任意の自然数\(N\)を\(k\)進法で\({a_{l}a_{l-1}\cdots a_{0}}_{\left(k\right)}\)と表記したとき、

\(\begin{eqnarray} N &=& \sum_{i = 0}^{l}a_{i}k^{i} \\ &=& a_{0}\times k^0+a_{1}\times k+a_{2}\times k^{2}+\cdots +a_{l}\times k^{l} \end{eqnarray}\)

ということを意味している。2進数を例として出せば、10進数での11

\(\begin{eqnarray} 11 = 1\times 10^0+1\times 10 \end{eqnarray}\)

は2進数での\(1011_{\left(2\right)}\)であって

\(\begin{eqnarray} 11 = 1\times 2^0+1\times 2+0\times 2^2+1\times 2^3 \end{eqnarray}\)

を意味する。さらに3進数で表記すると\(102_{\left(3\right)}\)であって

\(\begin{eqnarray} 11 = 2\times 3^0+0\times 3^{1}+1\times 3^{2} \end{eqnarray}\)

である。

以上より、\(k\)進法で\({a_{l}a_{l-1}\cdots a_{0}}_{\left(k\right)}\)と書いたときの各\(a_{i}\)は、自然数\(N\)を\(k\)進法で足し算にばらしたときの係数が書いてあることが分かる、というよりそういう定義。

\(k\)進法表記に変換するときの考え方

与えられた10進数の入力を\(k\)進法表記に変換するとき、重要になるのは以下の等式である。

\(\begin{eqnarray} N &=& \sum_{i = 0}^{l}a_{i}k^{i} \\ &=& a_{0}\times k^0+a_{1}\times k+a_{2}\times k^{2}+\cdots +a_{l}\times k^{l} \end{eqnarray}\)

c++において、整数同士の割り算では端数は切り捨てられる。
従ってこの式から分かるように、各\(a_{i}\)を求めるには、\(k^{i}\)で割った後に\(k\)で割ったあまりを取ればよい。
最初の\(k^{i}\)で割ったときに\(k^{i-1}\)までの項が全て0になり、後に\(k\)の剰余を考えることで\(k^{i+1}\)以降も全て消え去るからである。
こうして、\(a_{i}\)のみを取り出すことが出来る。

実装例

以上の考え方に基づき、10進数表記を\(k\)進数表記に直す実装例は以下のようになるであろう。¹

string ten2k(int n, int k){
 string s = "";
 if(n == 0) return "0";
 if(k == 1){
  for(int i = 0;i < n;i++) s += '1';
  return s;
 }
 while(n > 0){
  s += to_string(n % k);
  n /= k;
 }
 reverse(s.begin(),s.end());

 return s;
}

whileループの中で各桁を取り出しているが、それをそのまま返してしまうと表記が冪の小さい順に並んでしまうのでreverseでひっくり返している。
また、あまり使わないかもしれないが1進数表記に直そうとするとwhileループが無限に回ってしまうので、例外として処理した。
計算量は\(O\left(N\right)\)。
自分の環境でうまく動くことは一応確認してある。
(2021.10.12 追記)
\(n = 0\)の時に空文字を返してしまうので別途処理した。