63
правки
Изменения
→Алгоритм
{{---}} Для каждого нечетного <tex>N, A</tex> определим симол Якоби <tex>(\frac{N}{A})</tex> как <tex>\prod\limits_{i=1}^k QR_{P(i)}(A)</tex>, где <tex>P_1, ... , P_k</tex> это простые делители (не обязательно различные) числа <tex>N (N = \prod\limits_{i=1}^k P_i)</tex>. Заметим что сивол Якоби вычислим за <tex>O(logA * logN)</tex>
{{---}} Для каждого нечетного составного <tex>N, |\{A \in [N - 1]: gcd(N, A) = 1 \,and\,(\frac{N}{A}) = A^{\frac{N - 1}{2}}\}| \le \frac{1}{2}</tex> <tex>\,| \{A \in [N - 1]: gcd(N, A) = 1\}|</tex>
===Проверка двудольного графа на существование в нем полного паросочетания===
