Сигнал задачи
Когда применять
Когда задача использует делимость, большие степени, вычисления по модулю или много запросов о простых числах.
Как выбрать подход
- Алгоритм Евклида даёт НОД; расширенный вариант дополнительно находит коэффициенты Безу и помогает решать линейные сравнения.
- Обратный элемент по модулю существует только при gcd(a, m) = 1; формула a^(m−2) применима для простого m и a, не делящегося на m.
- Решето Эратосфена выгодно для всех простых до общего предела; для одного большого числа лучше проверка делителей или подходящий тест простоты.
- Быстрое возведение в степень работает для любой ассоциативной операции с нейтральным элементом, включая умножение матриц.
Сложность
- Алгоритм Евклида: O(log min(|a|, |b|)) времени и O(1) памяти в итеративной форме.
- Быстрое возведение в степень: O(log e) операций для неотрицательной степени e, память O(1) в итеративной форме.
- Решето Эратосфена до N: O(N log log N) времени и O(N) памяти.
- Сложение и умножение по модулю считаются O(1) только для машинных чисел; для длинной арифметики стоимость зависит от числа разрядов.
Границы и ошибки
- Остаток отрицательного числа в C++ может быть отрицательным; перед сравнением результат нормализуют.
- Произведение может переполниться до взятия по модулю; нужен достаточно широкий тип или безопасное модульное умножение.
- Нельзя делить по модулю, не проверив существование обратного элемента.
- В решете 0 и 1 не простые, а проверка i · i должна учитывать переполнение типа.