Про простые числа и делители.

  1. Решето Эратосфена.
    1. Алгоритм.
    2. Почему работает за O(NloglogN)
    3. Как можно посчитать списки делителей для всех чисел от 1 до N за O(NlogN).
  2. Разложение за O(sqrt(N))
  3. Сколько делителей у числа за O(sqrt(N))
  4. Для каждого числа получить список его делителей.
  5. Для каждого числа получить список его простых делителей.
  6. Сколько нулей на конце N? За O(logN).
  7. Д.З. Посчитать сумму - сколько делителей у чисел от 1 до N. За O(sqrt(N)).
  8. Not read Посчитать сумму - сколько простых делителей у чисел от 1 до N. За O(sqrt(N)).
  9. Д.З. Посчитать сумму по всем K = 1..N - сколько нулей на конце K! (за O(sqrt(N)), можно быстрее).

Обзор того, что бывает в мире.

  1. Разложение за O(N1/4)
  2. Проверка на простоту за O(logN)
  3. Посчитать число простых от 1 до N за O(N2/3)

Про уравнения и цикл FOR.

  1. AX + BY = C
  2. Д.З. AX + BY = C, A и B - простые, [A,B > 0] (задача G с контеста)
  3. Д.З. Сколько существует троек чисел A, B, C <= N : 3A + 5B = C
  4. Сделать холодильник размера N с целыми сторонами и минимальной площадью поверхности.
    1. Решение за O(N3)
    2. Решение за O(N1/2*N1/3)
    3. Решение за O(D(N)*N1/3)

[L,R]

  1. Сколько чисел на отрезке [L,R] не кратны P ?
  2. Сколько чисел на отрезке [L,R] состоят только из 0 и 1 в десятичной записи. L, R <= 1018.
  3. Сколько чисел на отрезке [L,R] состоят из цифр из множества D в десятичной записи. L, R <= 1018.
  4. Д.З. Число чисел от L до R, состоящих только из цифр из множества D и кратных M, M <= 100, 1 <= L, R <= 1018

Вычисления.

  1. Вычисления по модулю. Сложение, умножение.
  2. Быстрая степень за O(log).
  3. Умножение чисел порядка 1018 по модулю.
  4. Обратное. Алгоритм Евклида. O(logM).
  5. Обратное по теореме Ферма. O(logM) + Время чтобы найти Phi(M).
  6. Д.З. Обратные для всех за O(N).