Модульное умножение больших чисел

Если вы хотите избежать целочисленного переполнения, вы можете преобразовать

(a * b * c) % d

в

((((a % d) * (b % d)) % d) * (c % d)) % d

In C:

unsigned long work(unsigned long a, unsigned long b, unsigned long c, unsigned long d)
{
    unsigned long r = a % d;
    r *= b % d;
    r %= d;
    r *= c % d;
    r %= d;
    return r;
}

Однако он все еще может переполняться, но реже, чем наивная версия. Если вы хотите быть абсолютно уверены, что он не переполнится, вам следует использовать некоторую форму библиотеки больших чисел, например gmplib. Использование будет выглядеть так:

unsigned long work(unsigned long a, unsigned long b, unsigned long c, unsigned long d)
{
    mpz_t tmp, res;
    unsigned long r;
    mpz_init_set_ui(tmp, a);
    mpz_mul_ui(res, tmp, b);
    mpz_mul_ui(tmp, res, c);
    mpz_mod_ui(res, tmp, d);
    r = mpz_get_ui(res);
    mpz_clear(res);
    mpz_clear(tmp);
    return r;
}

Возможно, Gmplib поддерживает прямую установку результата в ту же переменную, что и один из операндов, но я не уверен. Вы должны проверить это в документации.