Изменения
Нет описания правки
# Задан многочлен $A(x) = \sum\limits_{i=0}^{n - 1} a_i x^i, a_0 \neq 0$. Найдите такой многочлен $B(x)$, что $A(x) \times B(x) = 1 + x^n Q(x)$ для какого-то многочлена $Q(x)$ за $O(n \log^2 n)$.
# То же самое за $O(n \log n)$.
# Какой критерий существования решения и как алгоритм восстановления числа в КТО, если убрать требование взаимной простоты модулей $m_1$ и $m_2$?
# Чему равна сумма всех чисел от 0 до $n-1$, взаимнопростых с $n$?
# Найдите $\frac{n!}{p^k} \bmod p$, где $p^k$ - максимальная степень вхождения $p$ в $n!$, за $O(p \log n)$
# Докажите, что $gcd$ последовательных чисел Фибоначчи равен 1.
# Докажите, что $gcd(F_n, F_m) = F_{gcd(n, m)}$.
# Для заданных $a$ и нечетного простого $p$, проверьте, что существует $x$: $x^2 = a \bmod p$ за $O(\log p)$
# Решите задачу дискретного логарифма для нечетного простого модуля $p$ вида $2^k + 1$ за $O(\mathop{poly}(k))$.
</wikitex>
