Aleksandr Sharahov, давай еще пару мыслей.

Я вспомнил логарифмирование и таблицы Брадиса и криптографию.

В сущности мы ищем функцию вида
xquotientShaDivMod10(x)1001111112211331..21122222

Для символической формы записи (десятичная система) данная функция - удобна.

Для произвольного делителя (например 77) мы можем, рассматривать нашу функцию
как криптографическую и создав таблицы наподобие книги кодов. Дело техники - искать
в ней по ключу. И опять-же операция целочисленного деления исключена из алгоритма
поиска.

Для очень больших делителей близких к 2^32 наша таблица будет выглядеть
удивительно разреженной. Представьте себе. А остаток от деления будет
почти линейно связан с делимым (похоже на поправку в таблице Брадиса).
Здесь есть много путей оптимизации (Карно, Квайн) и все они так-же не
используют деление в явном виде.

P.S. Все что я писал есть brainstorm и я могу быть с ним не согласен.