Как рассчитать модуль вида (a * b)% c?

Question

Как рассчитать модуль формы (a * b)% c?

Я хочу вычислить модуль умножения двух чисел типа int, где они почти находятся в стадии переполнения ...

здесь c также int

Answer 1

(a * b) % c == ((a % c) * (b % c)) % c

Answer 2

А как насчет ((a % c) * (b % c)) % c? В зависимости от вашей архитектуры это может быть быстрее или медленнее, чем приведение к большему типу.

Answer 3

Вы можете разыграть a и c до long long, поэтому умножение не будет переполнено.

((long long)a * (long long)b) % c