Как быть если остаток от деления не помещается в беззнаковый тип?

У меня есть два беззнаковых числа и требуется найти остаток от деления суммы этих чисел на третье, также беззнаковое число. Как это сделать аккуратно, если учитывать, что сумма двух беззнаковых вообще говоря не обязана влезать в тип по размеру (т.е. возможно переполнение)

Ответ

Алгоритм может быть такой. Берете остатки от деления каждого делимого на делитель. Затем берете разницу между делителем и одним из остатков. Вычитаете эту разницу из второго остатка, если она превосходит второй остаток, или складываете остатки, если они меньше в сумме делителя и получаете окончательный остаток.
Пусть имеются два беззнаковых числа x и y и делитель d. Тогда остаток r от деления x + y на d можно вычислить так.
r1 = x % d; r2 = y % d;
r = r1 < ( d - r2 ) ? r1 + r2 : r1 - ( d - r2 );
Вот пример функции для типа unsigned int на C/C++
unsigned int remainder(unsigned int x, unsigned int y, unsigned int d) { unsigned int r1 = x % d; unsigned int r2 = y % d;
return r1 < (d - r2) ? r1 + r2 : r1 - (d - r2); }