ABC192 D Base n
まず問題文の誤読に注意. 条件を満たす整数$ nの個数を求めるのではなく, $ Xを$ n進法の数としてみなした値の種類数($ Xのとりうる値の数)を求めるのである.
$ Xの長さを$ Nとおく.
$ N = 1のとき, どんな整数$ nに対しても$ Xの値は等しくなる. よってとりうる種類数は0か1であり, これは$ Xを数値としてみた際$ M以下かどうか判定すればよい.
$ N \geq 2のときは単調性があるので二分探索をすればよい.
細かい実装上の注意が2つある.
二分探索の際, $ lの値は$ d + 1ではなく$ dにすること
途中でオーバーフローしないように適切に処理すること
これらを適切に実装することで正しい答えを求めることができる. 計算量は$ O(N \log N)である.