Convert Base(進数変換) (math/number-theory/convert-base.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2024-05-01 23:44:47+09:00
• Include: #include "math/number-theory/convert-base.hpp"

与えられた 10 進数を進数変換します。

convert_base

vector< T > convert_base(T x, T b)

x を b 進数に変換した結果を返します。

計算量

• $O(\log_b x)$

Verified with

• test/verify/aoj-0233.test.cpp

Code

template <typename T>
vector<T> convert_base(T x, T b) {
  vector<T> ret;
  T t = 1, k = abs(b);
  while (x) {
    ret.emplace_back((x * t) % k);
    if (ret.back() < 0) ret.back() += k;
    x -= ret.back() * t;
    x /= k;
    t *= b / k;
  }
  if (ret.empty()) ret.emplace_back(0);
  reverse(begin(ret), end(ret));
  return ret;
}

#line 1 "math/number-theory/convert-base.hpp"
template <typename T>
vector<T> convert_base(T x, T b) {
  vector<T> ret;
  T t = 1, k = abs(b);
  while (x) {
    ret.emplace_back((x * t) % k);
    if (ret.back() < 0) ret.back() += k;
    x -= ret.back() * t;
    x /= k;
    t *= b / k;
  }
  if (ret.empty()) ret.emplace_back(0);
  reverse(begin(ret), end(ret));
  return ret;
}

Back to top page