(This solution has not been evaluated for worst-case complexity, so it may not pass depending on the test cases or the language, but I got an AC by PyPy3.)

[Solution]

\(b\) must be a divisor of \(N\) or a divisor of \(N-1\) because the ones digit of \(N\) in base \(b\) is either \(0\) or \(1\). Check all the possible divisors.

[Time Complexity]

The enumeration of divisors can be done in \(O(N^{\frac{1}{4}})\) time or so using Pollard’s rho algorithm for prime factorization.

The confirmation can be done in \(\log N\) time for each divisor. The overall time complexity is \(O(T(N^{\frac{1}{4}} + \displaystyle\max_{1\le n\le N}{f(n)} \log N))\) or so, where \(f(n)\) is the number of divisors of \(n\).

According to this website, integers up to \(10^{18}\) have a maximum of \(f(897612484786617600)=103680\) divisors, which is a little worrying, butI was able to get an AC by reusing the previous results when the same \(N\) appeared multiple times.

[Code Example]

AC Code (PyPy3)