問題

D – Base n

プログラミング初級者から上級者まで楽しめる、競技プログラミングコンテストサイト「AtCoder」。オンラインで毎週開催プログラミングコンテストを開催しています。競技…

atcoder.jp

記録

• 2022/3/17　解法わからず。

解法

• X が \(1\) 桁のときは注意する。
• 二分探索で何進数までいけるかを調べる。

コード例

#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
using namespace atcoder;
using ll = long long;
using P = pair<int, int>;
#define rep(i, n) for(int i = 0; i < (n); ++i)
// using mint = modint998244353;
// using mint = modint1000000007;
// const int mod = 1000000007;
// const ll INF = 1LL << 62;
// const int INF = 1001001001;

int main() {
  string X;
  ll M;
  cin >> X >> M;

  int n = X.size();

  if(n == 1) {
    if(stoi(X) <= M) {
      cout << 1 << endl;
    } else {
      cout << 0 << endl;
    }
    return 0;
  }

  int mx = 0;
  rep(i, n) { mx = max(X[i] - '0', mx); }

  ll ac = mx;
  ll wa = M + 1;

  while(1 < wa - ac) {
    ll mid = (ac + wa) / 2;
    ll v = 0;
    rep(i, n) {
      if(M / mid < v) {
        v = M + 1;
      } else {
        v = v * mid + (X[i] - '0');
      }
    }

    if(v <= M) {
      ac = mid;
    } else {
      wa = mid;
    }
  }

  cout << ac - mx << endl;

  return 0;
}