Теория чиселРешето ЭратосфенаНОДМатематика
1 мин чтение
Теория чисел и Модульная арифметика
Алгоритм Евклида, расширенный НОД, линейное решето Эратосфена за O(N), бинарное возведение в степень binpow и малая теорема Ферма.
Исходная заготовка: полнота объяснения и примеров ожидает редакторской проверки.
Алгоритм бинарного возведения в степень за
cpp
long long binpow(long long a, long long b, long long m) {
long long res = 1;
a %= m;
while (b > 0) {
if (b & 1) res = (__int128)res * a % m;
a = (__int128)a * a % m;
b >>= 1;
}
return res;
}Что дальше?
Вернитесь к обучению и выберите следующий материал.
Изучено — к обучению →Отметка сохранится в этом браузере. Её можно отменить или снять кнопкой «Изучено».