This kata definitely consists of two tasks:
First part is a nice puzzle. As for the second one, it's pretty easy to come around with a fixed array of bad integers. This array can either be hardcoded or calculated outside of the function. Both these ways feel like cheating to me.
So it's kinda weird: you have some performance problems to deal with, but they can be solved with the same computational complexity (linear) as the dumb algorithm, just changing the order a little bit.
IHMO, you should either remove the performance part from this kata (so that the stupid solutions like sum(1 if is_bad(i) else 0 for i in range(a, b+1)) work), or require a solution of logarithmic complexity.
sum(1 if is_bad(i) else 0 for i in range(a, b+1))
Or maybe you can split this kata in two: the first one will be very simple allowing the most obvious solution, but the second one should pose the performance problem to its full.
It should be stated whether all options should be taken or only one (and which one exactly), e.g. what's the result of these:
a = [1, A] b = [0, X] t = 1
a = [2, A] b = [0, X] t = 2