Модулярная арифметика: почему (a - b) % m бывает отрицательным и как считать вычитание правильно?
Считаю разность по модулю (a - b) % MOD, и иногда получаю отрицательное число, из-за чего потом всё ломается (например, при выводе или индексации). В Python такого нет, а в C++ есть. Почему так и как писать вычитание/сложение по модулю надёжно?
2 ответа
В C++ оператор % для отрицательного левого операнда возвращает результат со знаком делимого: (-3) % 7 == -3, а не 4. Поэтому если a < b, то (a - b) % MOD будет отрицательным. В Python % всегда возвращает неотрицательный остаток (другая семантика), отсюда разница.
Каноничный приём для вычитания по модулю — добавить MOD и взять остаток ещё раз:
long long sub(long long a, long long b, long long m) {
return ((a - b) % m + m) % m; // гарантированно в [0, m)
}
Здесь (a - b) % m лежит в (-m, m), после + m — в (0, 2m), и финальный % m загоняет в [0, m).
Для сложения переполнения по знаку нет, но следи, чтобы не переполнить тип при многих слагаемых:
long long add(long long a, long long b, long long m) { return (a + b) % m; }
Всё это O(1). Главное правило: после любого вычитания по модулю нормализуй результат в [0, m). Это спасает от RE при использовании результата как индекса массива.
Маленький, но реальный баг из практики: люди пишут (a - b + m) % m и думают, что защитились. Но если a - b может быть меньше -m (например, накопили несколько вычитаний без нормализации), одного + m не хватит и результат снова отрицательный. Поэтому либо нормализуй после каждой операции, либо используй ((a - b) % m + m) % m — двойной % устойчив при любом одиночном вычитании, потому что сначала загоняет в (-m, m).