【C++】文字列SをM以下の値に表せる基数（進数）の個数を求めるプログラム

問題概要

数字だけで構成された文字列 S と整数 M が与えられます。S に含まれる最大の桁の値を d とします。d+1 以上の整数 n を基数として選び、文字列 S を n 進法の数として解釈したとき、その値が M 以下になるような基数は何通り存在するかを求めます。

例えば、S = "999"、M = 1500 という入力の場合、出力は 3 になります。10進数として解釈すると 999、11進数では 1197、12進数では 1413 となり、13進数以上では値が 1500 を超えてしまうため、条件を満たすのはこの 3 通りだけです。

アルゴリズムの考え方

基数 n が大きくなるほど、S を n 進数として解釈した値は単調に増加します。この性質を利用すれば、「値が M 以下になる最大の基数」を二分探索で効率的に求められます。有効な基数の範囲は d+1 からその最大値までなので、答えは「最大の基数 − d」で求まります。

解法の手順

1. 文字列 S の長さが 1 の場合、その値が M 以下なら 1 を、そうでなければ 0 を返します。
2. S を走査して、含まれる最大の桁の値 d を求めます。
3. 探索範囲を left = d、right = M + 1 として二分探索を開始します。
4. 各ステップで中央値 mid を取り、S を mid 進数として評価します。オーバーフローを防ぐため、計算途中で v > M / mid となった時点で v を M + 1 に設定します。
5. 評価結果 v が M 以下なら left = mid、そうでなければ right = mid と更新します。
6. ループ終了後、left − d を返します。

if size of S is same as 1, then:
    if numeric value of S <= M, then:
        return 1
    Otherwise
        return 0
d := 0
for each character c in S, do
    d := maximum of d and (c - ASCII of '0')
left := d
right := M + 1
while right - left > 1, do:
    mid := (left + right) / 2
    v := 0
    for each character c in S, do
        if v > M / mid, then:
            v := M + 1
        Otherwise
            v := v * mid + (c - ASCII of '0')
    if v <= M, then:
        left := mid
    Otherwise
        right := mid
return left - d

C++による実装例

以下のコードで実際の動作を確認できます。

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

int solve(string S, int M){
    if (S.size() == 1){
        if (stoi(S) <= M)
            return 1;
        else
            return 0;
    }
    int d = 0;
    for (char c : S)
        d = max(d, int(c - '0'));
    long left = d;
    long right = M + 1;
    while (right - left > 1){
        long mid = (left + right) / 2;
        long v = 0;
        for (char c : S){
            if (v > M / mid)
                v = M + 1;
            else
                v = v * mid + (c - '0');
        }
        if (v <= M)
            left = mid;
        else
            right = mid;
    }
    return left - d;
}
int main(){
    string S = "999";
    int M = 1500;
    cout << solve(S, M) << endl;
}

入力

"999", 1500

出力

3

計算量

二分探索の反復回数は O(log M)、各反復での文字列の評価には O(|S|) かかるため、全体の時間計算量は O(|S| log M) です。巨大な基数に対しても高速に動作する点が、この手法の大きな利点といえます。