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

1. Алгоритмы в теории чисел

Преподаватель:
Григорьева Анастасия Викторовна
[email protected]
мат-мех, СПбГУ
2021

2. Что будет сегодня?

Технические вопросы
Теория
Задачи на ТЧ
Контест с консультацией по алгоритмам
Полный разбор задач вечером
2

3. Инструменты

ideone.com
informatics.msk.ru
3

4. Теория

5. Арифметика остатков

6. Определение

Обычно обозначается %
6

7. С++/python

r=a%b
Когда a > 0 и b > 0, то все понятно и ответ один
Но в python: −12%5 = 3
а в C++
−12%5 = −2
Потому что остаток от деления в С++ это то, что отбросило
целочисленное деление.
То есть -7/2 = -3, поэтому -7%2 = -1
Деление там = отбросить дробнуй часть(=округление к нулю)
Чтобы остаток от деления всегда соответствовал данному выше
определению, можно отдельно разбирать случай при a<0 или писать
выражение для нахождения остатка в виде (a%b+b)%b
7

8. Python

1,7 % 0,25 = 0,2
1,7 // 0,25 = 6
-5 // 2 = -3
-5 % 2 = 1
7 / 2 = 3,5
= 170:25
round(x) – математическое округление
d = math.floor(d) – целая часть числа
8

9. Сравнимость по модулю

9

10.

10

11. Обратные элементы

11

12. Как найти обратный элемент по простому модулю?

Малая теорема Ферма нам поможет:
12

13. Алгоритм быстрого возедения в степень

13

14. А зачем нам обратный элемент может понадобиться?

14

15. Кто хочет потренироваться: Задача Обратный элемент №4189

15

16. НОД

17. НОД и его свойства

Наибольший общий делитель (НОД) двух целых чисел a и
b, a≠0 или b≠0, — наибольшее целое число, которое
является делителем a и b одновременно.
gcd (от английского "greatest common divisor").
17

18. Алгоритм Евклида (Задача №199)

18

19. НОД и НОК

19

20. Представление числа №1037. Вместе.

20

21. Решение

На доске
21

22. Оптимизируем

Видите,
какая старая
фотография
кода?
Да, это
Pascal
Совет: при такой реализации sqrt(N) вычисляется при каждой
Итерации цикла while. Этого можно избежать, если заранее
вычислить эту величину и использовать в условии цикла её
значение. Хотя современные компиляторы сами это делают, я
проверяла – засекала время. Но хорошие привычки – это
полезно.
Заметим, что если N – простое, то НОД(А, В) = 1 для любых A и
B, дающих в сумме N, поэтому можно вывести любые
натуральные числа, сумма которых равна N
22

23. Делители числа

24. Оптимизация перебора

До какого искать и почему?
sqrt
А если нужно узнать все делители?
до sqtr и парные к ним. Осторожнее с
полными квадратами
А как разложить на простые множители?
Делим, пока делится, если нет – переходим
к следующему
24

25. Зачем вам может понадобиться искать делители числа?

Например в задаче «Кубическое
уравнение» №1040
Тут нужно решить в целых числах. Если в
вещественных, то это уже бинарным
поиском №3722
25

26. Кубическое уравнение №1040

26

27. Решение

На доске
27

28. Проверка числа на простоту

Есть алгоритм «Решето
Эратосфена», но его потом

29. Проверка на простоту. Задача № 310 Подсказка

29

30. Решение

30

31. Контест

32. Можно задавать нам вопросы в процессе решения

1.
2.
3.
4.
5.
6.
7.
8.
Сокращение дроби №27
Количество делителей №341
Остаток от деления на цифру №868
Представление чисел №1037
Возведение X в степень N по модулю P № 111741
Дружественные числа №635
Тройки чисел №29
* Разложение на простые № 1455
32

33. Разбор контеста

34. Сокращение дроби №27

34

35. Решение

Чтобы сократить дробь, нужно числитель и знаменатель
разделить на их НОД (наибольший общий делитель)
НОД(a,b) не превосходит их, то есть в ограничениях задачи
<100. Его можно найти перебирая все числа от 100 до 1, пока не
встретится число, на которое делится и a и b
Сработает даже если a<=0
А можно написать функцию, вычисляющую НОД. Это один из
обязательных для запоминания блоков кода.
35

36. Количество делителей №341

36

37. Решение

37

38. Остаток от деления на цифру №868

38

39. Решение

Смодулируем процесс деления столбиком длинного числа на
короткое с тем упрощением, что нам не надо запоминать целую
часть от деления
Основной процесс: берем старший разряд, запоминаем его
остаток от деления на k, потом приписываем к получившемуся
остатку следующий разряд
ost*10+n[i]
и т.д. Получившийся после обработки всех разрядов остаток и есть
ответ на задачу
ost = (ost*10+n[i]) % k
39

40. В python

Одной строчкой решается:
#получили a и b
print(a%b)
Иногда питон весьма полезен
40

41. Возведение х в степень N по модулю P. № 111741

На вход программе подаются 3 целых неотрицательных числа
x, N и P, не превосходящих 2 * 109. Кроме того P > 0.
Требуется вычислить значение x в степени N по модулю P.
41

42. Решение

Бинарное (быстрое) возведение в степень
и возвращаем значение уже по модулю P
42

43. Подарок для любителей питона

43

44. Дружественные числа №635

220=
1+2+4+71+142
(все делители
числа 284)
284 =
1+2+4+5+10+11
+20+22+44+55+
110
(все делители
числа 220
44

45. Решение

Предподсчетом. Таких чисел очень мало в
пределах 1 000 000, поэтому получить их
всех можно заранее, на своем компьютере,
минуты за 4, и внести в код программы. Но
использовать все равно нужно
оптимальный алгоритм – не забыть до
корня из числа считать делители, иначе это
не 4 минуты будет считаться.
Еще на предподсчёт:
№ 3589. Фибоначчиева система счисления
№629. Совершенные числа
№113323. «Кто хочет стать миллионером?»
45

46. Тройки чисел №29

46

47. Решение

Возвести в квадрат
Но не просто так, а перенеся корень из b в правую часть
a = b + 2sqrt(bp) + p
Поскольку a,b и p – целые числа, то и sqrt(bp) – целое число, т.е.
b равно произведению p и квадрата некоторого целого числа
b = pn^2, a = p(n-1)^2
Т.о. для каждого p из отрезка [N,M] требуется найти все такие n,
что
N<= p(n-1)^2 < pn^2 <= M
47

48. Оптимизируем

Разделим на p все части и извлечем корень
Sqrt(N/p) <= n-1 < n <= Sqrt(M/p)
Т.о., количество решений на 1 меньше, чем количество
целых чисел на отрезке [Sqrt(N/p);Sqrt(M/p)]
Проверяем на простоту каждое число от N до M и находим
кол-во решений для каждого из найденных простых чисел
указанным выше способом
48

49. Разложение на простые № 1455*

49

50. Решение

50