есть подход который позволяет делить довольно просто, и он также работает для других подобных операций. это похоже на "powering by squaring" — бинарное возведение в степень. Недостаток — он более медленный асимптотически. пусть битовая длина длинных чисел na, nb, основание системы счисления есть BASE = 2^base (где base не обязательно целое, то есть основание и десятичным быть может, типа 10000). Чтобы поделить два числа данный метод потребует na * (na — nb + 1) / base операций, в (третьем?) томе кнута описан алгоритм работающий за na * (na — nb + 1) / (base^2) операций.

void DivMod(int a, int b, int& Div, int& Mod) {
    int z = 1;
    int k = 0;
    while (a >= b) {
        b <<= 1;
        z <<= 1;
        k++;
    }
    Div = 0;
    while (k > 0) {
        b >>= 1;
        z >>= 1;
        k--;
        if (a >= b) {
            a -= b;
            Div += z;
        }
    }
    Mod = a;
}