Инварианты и делимость
Возвращаемся к методу инвариантов уже на материале делимости. Во многих олимпиадных задачах действия меняют числа, но не меняют их делимость по модулю.
Инварианты по делимости позволяют:
- сразу понять, что результат невозможен
- сократить количество вариантов и время на решение задачи
- заменить перебор строгим доказательством
Научимся:
- находить, что остаётся неизменным с точки зрения делимости
- находить величины, которые сохраняются по модулю
- использовать делимость как инвариант
- доказывать невозможность некоторых действий или конфигураций