SOMPO HD プログラミングコンテスト2021 D - Base n (400)
ある$ n進数でできるなら$ n-1進数以下でもできるので、二分探索で作れる範囲を求められる
$ Xを$ n進数として見るとオーバーフローするかもしれないので$ Mを$ n進数に変換することにする
$ n進数に変換することにするときはとりあえず配列でそれぞれの桁の値を持っておく
二分探索の判定関数では以下を行う
$ n進数に変換した$ Mのが$ Xより長かったらOK、短かったらNG
同じ長さだったら各桁を見て$ Xの方が大きかったらNG
$ Mの方が大きかったり、最後まで同じだったらOK
一回の判定が$ O(|X|)、二分探索が$ O(\log M)なので、全体で$ O(|X|\log M)