Здравствуйте, T4r4sB, Вы писали:

TB>Шо, так можно что ли. Это же брутфорс наглый.

Так в расчёте на брутфорс и сделаны условия: "до 10тыс".
Я даже больше скажу: если программа должна быстро обработать стопятьсот запросов, то можно один раз посчитать (даже во время компиляции) табличку

const int num_okays_table[10002]; // количество нужных чисел на интервале [0;i) для i = 0..10001

int num_okays(int M, int N) {
  assert(0 <= M && M <= N && N <= 10000);
  return num_okays_table[N+1] - num_okays_table[M];
}