Арифметика и числовые алгоритмы

Тематический план

• 

  Общее

  Сын принёс двойку по математике
  за контрольную. Взял, да решил
  один из примеров. Получился ответ "5".
  Смотрю на его ответ - "101". Думаю:
  "Ну и чего тут неправильного?!"...

  (С)bash.org.ru

  • Теоретический материал по арифметике и числовым алгоритмам Файл
• 

  Тема 1

  Арифметические алгоритмы

  • Условия задач
  • Теоретический материал: Решето Эратосфена (М.Иванов) Гиперссылка
  • Теоретический материал: Функция Эйлера (М.Иванов) Гиперссылка
  • Теоретический материал: Бинарное возведение в степень за О(log N) (М.Иванов) Гиперссылка
  • Теоретический материал: Обратный элемент в поле по модулю (М.Иванов) Гиперссылка
  • Теоретический материал: Дискретное логарифмирование (М.Иванов) Гиперссылка
  • Теоретический материал: Линейное модулярное уравнения с одним неизвестным (М.Иванов) Гиперссылка
  • Теоретический материал: Китайская теорема об остатках. Алгоритм Гарнера (М.Иванов) Гиперссылка
  • Теоретический материал: Нахождение степени делителя факториала (М.Иванов) Гиперссылка
  • Теоретический материал: Вычисления факториала по модулю (М.Иванов) Гиперссылка
  • Теоретический материал: Первообразный корень. Алгоритм нахождения (М.Иванов) Гиперссылка
  • Теоретический материал: Дискретное извлечение корня (М.Иванов) Гиперссылка
• 

  Тема 2

  Наибольший общий делитель и алгоритм Евклида

  • Теоретический материал: НОД и НОК, алгоритм Евклида (М.Иванов) Гиперссылка
  • Теоретический материал: Расширенный алгоритм Евклида (М.Иванов) Гиперссылка
  • Теоретический материал: Диофантовы уравнения с двумя неизвестными: AX+BY=C (М.Иванов) Гиперссылка
  • Вычисление НОД 2-х чисел Условия задач
  • Задачи, сводящиеся к вычислению НОД Условия задач
  • НОД n чисел, НОК, ... Условия задач
  • Расширенный алгоритм Евклида. Линейные диофантовы уравнения. Условия задач
  • Задачи на понимание и модификацию алгоритма Евклида Условия задач
  • Сложные олимпиадные задачи Условия задач
  • Теоретический материал: Обратный элемент в поле по модулю (М.Иванов) Гиперссылка
• 

  Тема 3

  Системы счисления

  • Целые числа Условия задач
  • Дроби Условия задач
  • Теоретический материал: Троичная сбалансированная система счисления (М.Иванов) Гиперссылка
• 

  Тема 4

  Битовые операции

  • Условия задач
  • Теоретический материал: Перебор всех подмасок данной маски (М.Иванов) Гиперссылка
• 

  Тема 5

  "Длинная" арифметика

  • Просто о "длинных" числах (В. Гуровиц) Файл
  • Теоретический материал (В.Гольдштейн) Файл
  • Теоретический материал (С++, М.Иванов) Гиперссылка
  • Реализация Книга
  • Условия задач
• 

  Тема 6

  Более сложные арифметические алгоритмы

  • Теоретический материал: алгоритм Карацубы и быстрое преобразование Фурье (А.Климовский) Книга
  • Умножение двух полиномов или длинных чисел с помощью Быстрого преобразования Фурье за O (N log N) (М.Иванов) Гиперссылка
  • Реализация БПФ в поле вычетов по модулю p (А.Ворожцов) Книга
  • Тест BPSW на простоту чисел за O (log N) (М.Иванов) Гиперссылка
  • Эффективные алгоритмы факторизации: Полларда p-1, Полларда p, Бента, Полларда Монте-Карло, Ферма (М.Иванов) Гиперссылка
  • Задачи на сложные теоретико-числовые алгоритмы Условия задач