Без девяток

Первое, что нужно понять — задачу на отрезке от l до r можно свести к задачам на отрезке от 1 до l и от 1 до r. Так как F(l..r) = F(1..r) - F(1..(l - 1))

Теперь нужно научиться считать количество чисел от 1 до какого-то r. Заметим, что числа, в которых нет девяток — это числа в девятеричной системе счисления. Воспользуемся теперь тем, что границы l и r не имеют девяток в своем представлении. Следовательно, все что там остается сделать — это перевести входные данные в десятичную систему счисления и вывести их разность.

К сожалению, F(l..r) = F(1..r) - F(1..(l - 1)) данная формула будет не совсем правильно работать в контексте данной задачи, так как значение l - 1 может содержать девятки. Поэтому ответом на задачу будет являться F(r) - F(l) + 1, где F(n) —десятичное представление девятеричного числа n.