Занятие №1. Арифметика и теория чисел [Густокашин]

Теория: Лекция                                                  [Все занятия]

Лекция является вводной, но все равно много интересного можно оттуда почерпнуть. В частности:
1) Нахождения НОД’а длинных чисел на основе формул:
gcd(2a, 2b)     = 2gcd(a,b)
gcd(2a, 2b+1)   = gcd(a,2b+1)
gcd(2a+1, 2b+1) = gcd(2(a-b),2b+1)
Хорошие формулы, уменьшающие накладные расходы. Осталось их только запомнить =)

2) Умножение двух матриц с предварительным транспонированием второй.

Практика:                                              [Официальная страница]
Учебные задачи
  Задача A. 
   [A-B]
   Такие задачи мы уже решали раньше в рамках темы Длинная арифметика.
   Задача B.
   [Целые точки отрезка]
   Если отрезок не параллелен осям координат, то достраиваем его до прямоугольного треугольника, где этот отрезок является гипотенузой, а катеты параллельны осям координат. После чего можно выйти на следующую формулу:
gcd(A,B) + 1, где A и B катеты прямоугольного треугольника. Стоит отметить тот факт, что формула работает и в том случае, если отрезок параллелен любой из оси координат.
   Задача С.
   [Разложение на простые]
   Сложность O(sqrt(N)). Можно смело ввести одну оптимизацию. Стоит заметить, что в строке 34 каждый раз пересчитывается верхняя граница внешнего цикла.
Олимпиадные задачи
  Задача А. 
   [Представление чисел]
   Рассуждаем. N = A + B. При этом нужно максимизировать gcd(A,B). 
A = a * gcd(A,B) 
B = b * gcd(A,B)
=> N = gcd(A,B) * (a + b). Главный вывод в том, что N делится на gcd(A,B) без остатка. Если мы хотим максимизировать gcd(A,B), зная N, то необходимо мизировать (a+b). Следовательно (a+b) – минимальный множитель N, отличный от 1.
Неплохо =). Теперь мы можем найти максимальный gcd(A,B) для любого N. Подумаем как найти сами числа A и B. A = a * gcd(A,B); B = b * gcd(A,B). Но мы не знаем a и b, а знаем только их сумму. Какие же a и b нужно выбрать? Думаем.
Ответ: любые натуральные.
Обратимся к примерам: 
    1) N = 16. a + b = 2. gcd(A,B) = 8. Следовательно a = 1 и b = 1, поэтому A и B определяются однозначно.
    2) N = 35. a + b = 5. gcd(A,B) = 7. Здесь может быть несколько случаев:
a = 1, b = 4;
a = 2, b = 3;
a = 3, b = 2;
a = 4, b = 1;
Понятно, что последние два случая являются зеркальным отображением первых двух, поэтому можно рассматривать только первые два случая. Как видно не важно какой из них мы выберем в качестве ответа. Для того, чтобы не плодить лишние if’ы можно a всегда брать 1. 
    3) N = 17. a + b = 17. gcd(A,B) = 1. В данном случае можно брать любое разложение числа N на слогаемые.
   Задача В.
   [Кинотеатр]
   Судя по ограничениям обычное моделирование ситуации не канает. Начинаем думать. Ко мне решение пришло, когда я нарисовал оба случая для случая n=5,m=7. После чего появились следующие выводы:
1)  Все элементы, которые останутся на своих местах будут находится на виртуальной главной диагонали матрицы.
2) Задача сводится к задаче B из первого блока учебных задач.
   Задача С.
   [Степень]
   Для начала разобьем исходное число А на простые множители в формате, представленном в лекции. Например число 12:
osn  = {2,3}
step = {2,1}, т.е. 12 = 2^2 + 3^1.
Очевидно, что каждый просто множитель из числа A должен входить как минимум один раз в число N. Но не факт, что получившееся число N будет удовлетворять требованиям задачи. Например для такого числа A:
osn  = {2,3}
step = {19,1}
Как быть? Необходимо увеличить число N в минимальное число раз, так чтобы оно удовлетворяло условию задачи.
Дополнительные олимпиадные задачи
   Задача А.
   [Марсианские факториалы]
   Для решения этой задачи сначала можно рассмотреть более простой случай. Будем искать ответ пока только для основания системы счисления = 10. Понятно, что ноль в конце факториала получится, если в разложении факториала на простые множители найдутся 2 и 5. При этом общее количество нулей будет равно количеству 5-ок в разложении факториала на простые множители.
Рассмотрим пример: N = 128. Сколько нулей будет в конце N! ?
Переберем все числа кратные 5, которые не превышают N:
5, 10, 15, 20, 25, 30, … , 120, 125 – всего N/5.
Как можно заметить в этом ряду есть числа, которые в своем разложении имеют несколько 5. Найдем все числа, которые имеют в своем разложении две пятерки:
25, 50, 75, 100, 125 – всего N/25.
Затем найдем числа, которые имеют 3 пятерки в своем разложении:
125 – всего N/125
Сложив количество элементов в этих трех рядах, мы найдем ответ на поставленный вопрос.
Как быть в случае, когда основания системы счисления отлична от 10. 0 в конце числа появится, если в его разложении на простые множители найдутся все простые множители из разложения основания системы счисления. Так например для основания 6(2*3) число 100! будет иметь 48 нулей, потому что 100! содержит 97 двоек и 48 троек. Все вычисления можно проводить в 10-ой системе счисления.
Тонким моментом является ситуация, когда основание системы счисления в своем разложении имеет несколько одинаковых множителей. Например найдем 1000! для osn = 72 = (2^3 * 3^2)
В разложении 1000! имеется 994 двойки и 498 троек. Количество же нулей в конце будет 249.
   Задача В.
   [Скорая помощь]
   Задача на углубленное понимание операций целочисленного деления и взятия остатка от деления. Перебираем количество квартир(от 1 до 1000) на одном этаже и в совокупности с параметрами K2,P2 и N2 определяем корректность перебираемого значения. Если после перебора выяснится, что только одно значение количества этажей являлось корректным, то значит входные данные оказались непротиворечивыми. Т.е. параметры N1 и P1 определяются однозначно. Если же не удалось подобрать количество квартир на одном этаже, либо N2>M, то значит решений нет. Если в качестве количества квартир на одном этаже подошло более одного значения, тогда определяем насколько однозначно можно определить параметры N1 и P1, согласно условию задачи.
   Задача С.
   [Проверьте равенство]
   Кромоздкая задача, в которой помимо того, что нужно реализовывать длинную арифметику, так еще и учесть целую череду частных случаев. Особое внимание к:
0^0 и 0^-1. В решении можно реализовать деление длинного на длинное, а можно этого не делать, если немного подумать.