Учебная задача A "Вычитание"
Вычитание необходимо было реализовывать аналогично сложению (т.е. делать "вычитание в столбик", лекция 1, раздел 4). Поскольку ограничения были очень небольшие и чисел всего два, можно было облегчить себе задачу:
1) Не обязательно было считать количество знаков в числах, т.е. просто выполнять вычитание нулей из нулей (перед этим нужно было заполнить массивы нулями).
2) Не обязательно хранить по несколько разрядов в одной "цифре". При хранении одного разряда облегчался вывод результата (и считывание выходных данных тоже).
При такой реализации задача не представляла особой программистской сложности.
Решение этой задачи помогло бы при реализации дополнительной олимпиадной задачи C.
Учебная задача B "Целые точки отрезка"
Несложно заметить, что отрезок, имеющий целые точки, отличные от концов отрезка, состоит из целого числа меньших одинаковых отрезков с целыми координатами. Нам необходимо подсчитать наибольшее количество таких отрезков, после этого подсчитать количество целых точек не составит труда. Обозначим количество отрезков за N. Понятно, что X координата исходного отрезка должна делится нацело на N (как и Y координата). Наша задача - найти наибольшее возможное значение N. Т.е. НОД(X, Y). Количество целых точек на 1 превышает количество отрезков, т.е. для решения задачи нужно было переписать реализацию поиска НОД (лекция 1, раздел 6) и прибавить к этому числу 1.
Учебная задача C "Разложение на простые"
Нетрудно понять, что число может иметь лишь один простой делитель, превышающий корень квадратный из этого числа(а может и не иметь). В случае наличия двух таких делителей, их произведение превысило бы данное число, что противоречит определению разложения на делители.
Обладая таким знанием легко понять, что разложение на простые делители возможно с помощью несложной модификации алгоритма проверки числа на простоту (лекция 1, раздел 5). При нахождении делителя выход из функции следовало заменить на цикл while делящий число на найденный делитель до тех пор, пока оно делится и вывод этого делителя.
Олимпиадная задача A "Представление чисел"
Обозначим наибольший общий делитель чисел A и B за X. Тогда A = X*M, B = X*K, N = X (K+M). Из этого соотношения можно понять, что X является делителем числа N. Кроме того, поскольку числа A и B должны быть натуральными, необходимо, чтобы K + M было больше либо равно 2. Таким образом, нам нужно было разбить число N на два делителя X и Y таким образом, чтобы Y был больше либо равен 2. Это делается простой модификацией алгоритма проверки числа на простоту (лекция 1, раздел 5), только вместо выхода из функции при нахождения делителя его необходимо было обработать. Мы искали меньший делитель (Y). Больший делитель X вычисляется как N/Y. В качестве ответа подходят числа X и N-X (их НОД равен X). В случае, если исходное число было простым (т.е. делители не были найдены), можно было вывести ответ 1 и N-1 (НОД слагаемых в любом случае равен 1).
Олимпиадная задача B "Кинотеатр"
В этой задаче необходимо было понять, что школьники, оставшиеся на своих местах, будут находиться на главной диагонали. Это можно было сделать как путем рисования и наблюдения, так и выводом уравнения прямых с помощью определения координат школьников по X и Y по номеру, приравниванию формул для двух случаев и решению системы уравнений.
Представим, что школьники сидят не в клетках, а в точках пересечения линий сетки (на клетчатой бумаге). Тогда школьник сидящий в левом верхнем углу будет иметь координаты (0, 0), а последний - координаты (N-1, M-1). Необходимо провести отрезок от первого школьника к последнему (главную диагональ) и посчитать количество целых точек на нем (в этих точках сидят школьники, которые остаются на своих местах). Это делается полностью аналогично учебной задаче B и ответ равен НОД(N-1, M-1) + 1.
Олимпиадная задача C "Степень"
Разложим число A на простые множители (см. учебную задачу C) и сохраним эти простые множители в массив primes, а степени их вхождения в соответствующие элементы массива powers_a. Внимательно изучив раздел лекции о разложении на простые множители (лекция 1, раздел 7), можно понять, что для того, чтобы N^N делилось нацело на A, необходимо, чтобы каждый простой множитель входил как минимум один раз. Таким образом в первом приближении число N вычисляется как произведение всех простых множителей числа A, взятых в первой степени. Однако, это условие необходимо, но недостаточно. Самый простой пример, когда это не будет работать: 8. Действительно, N в этом случае будет равно 2, а 2^2 не кратно 8.
Для решения этой проблемы введем "дополнительный" множитель, который назовем sup_mul. Его следует перебирать от 1 (найдется он достаточно быстро, в этом легко убедиться). Итак, теперь мы рассматриваем число N*sup_mul и пытаемся понять, делится ли (N*sup_mul)^(N*sup_mul) на A. Для этого необходимо построить разложение N*sup_mul по простым делителям числа A (они хранятся в массиве primes), степени, с которыми они входят в разложение сохраним в массив powers_n. Остальные простые делители нам неинтересны, т.к. не влияют на делимость на A. Функция проверки, является ли N*sup_mul ответом, должна умножать каждый из элементов powers_n на N*sup_mul и проверять, что результат умножения больше либо равен соответствующему элементу массиву powers_a (этот простой множитель входит в наше число со степенью, больше либо равной, чем он входил в разложение числа A, а значит число кратно A по этому множителю). Если для всех элементов это условие выполнено, то мы нашли ответ.
При реализации удобнее всего было написать функцию подсчета всех простых делителей без учета кратности и сохранения их в массив primes. Затем необходима функция, которая раскладывает переданное число по этим множителям (т.е. заполняет массив powers). При наличии таких функций решение должно было выглядеть примерно так:
primes = gen_primes(A);
powers_a = gen_powers(A, primes);
N = 1;
for i = 1, size(primes)
N = N * primes[i];
for sup_mul = 1, 32
powers_n = gen_powers(N*sup_mul, primes);
flag = 1;
for j = 1, size(primes)
if powers_n[j]*n*sup_mul < powers_a[j]
flag = 0;
if flag == 1
print N*sup_mul;
exit;
Дополнительная олимпиадная задача A "Марсианские факториалы"
Сначала научимся решать задачу для десятичной системы счисления. Количество нулей равно показателю степени числа 10^M, на которое делится число N. Число 10 представимо в виде произведения чисел 5 и 2, т.к. на каждое из чисел, кратных 5, обязательно найдется число, кратное 2, то ответом будет показатель степени числа 5^M. Для того, чтобы посчитать, на какую степень 5 делится N!, необходимо разделить число N на 5. Однако, это еще не будет ответом, т.к. дополнительный ноль в конце N! добавят числа, кратные 25 (т.к. 25*4=100, добавляет не один ноль, а 2). Т.е. при K=10 ответом будет N/5 + N/(5^2) + N/(5^3) + ...
Однако, не всегда все получается так хорошо. В частности, для системы счисления с основанием 12 есть два разбиения: 3*4 и 2*6. А для числа 9 и вовсе неприятное сочетание 3*3.
Допустим, что для каждого числа в разбиении (обозначим за X) существует дополнительное число (т.е., например, при разбиении 12 на 2*6, будем считать, что для каждой двойки найдется шестерка). Тогда количество нулей будет определяться, как F(X) = N/X + N/(X^2) + ...
Решим проблему, когда число X входит в разложение не в первой степени (например, 3*3). В таком случае, F(X) необходимо разделить на показатель степени, с которым число X входит в разложение числа K (ведь для получения нуля мы должны использовать несколько вхождений). Обозначим это количество за G(X).
Теперь перейдем собственно к решению задачи. Необходимо для K построить его разложение на простые множители, и для каждого из них подсчитать функцию G(X) - количество нулей, которое будет в конце, если для каждого вхождения X найдется дополнительный множитель, равный K/X. Для получения ответа необходимо выбрать минимум среди всех возможных значений функции G(X), это гарантирует нам, что дополнительные множители точно найдутся.
Красивое решение этой задачи занимает менее 30 строк, в ней даже не используются массивы.
Дополнительная олимпиадная задача B "Скорая помощь"
Если бы нам было известно количество квартир на этаже (X), то проверка корректности совершалась бы тривиальным образом:
P2 = K2/(M*X)+1;
N2 = K2%(M*X)/X + 1
Если оба эти условия выполнены (т.е. X - корректное количество квартир), то P1 и N1 вычисляются по таким же формулам.
Ограничения задачи позволяли за отведенное время перебрать все возможные значения X (от 1 до 1000). В случае, если корректность не была достигнута ни разу, выводим -1, если несколько раз - 0 0. Если же вариант X единственный, то достаточно рассчитать P1 и N1 по формулам.
Дополнительная олимпиадная задача C "Проверьте равенство"
Рассмотрим отдельно случаи неправильного задания числа (т.е. B<= 0 и A=0), а также сделаем необходимые проверки на случаи явного неравенства чисел (один из показателей отрицателен, другой положителен; одно из чисел отрицательно и возводится в нечетную степень, а результат другого вычисления положителен). Проверим случай, когда оба показателя степени равны 0, а числа не равны 0 (тогда ответ correct).
Теперь сосредоточимся на рассмотрении положительных чисел (отрицательные после проверок можно заменить на положительные).
Несложно понять, что число (10^100)^(10^100) будет иметь порядка 100*10^100 знаков и в нашу память никак не влезет (не говоря уже о времени вычисления. Что должно отвести от мысли попытаться подсчитать результат и сравнить его.
Аналогично, разложение числа 10^100 на простые множители невозможно (нам придется только перебирать все числа до 10^10, на что у нас не хватит времени). Так что этот вариант также невозможен.
Поскольку не один из точных методов, придуманных нами, оказался невозможен, воспользуемся приближенным.
Рассмотрим простой пример: равны ли числа 8^5 и 6^8? Проведем тест по модулю 3. Что это означает? Посчитаем остаток от деления 8 на 3 (X=2) и 6 на 3 (Y=0). Возведем быстрым возведением в степень (лекция 1, раздел 8) или воспользуемся цикличностью повторения остатков (составим "таблицу умножения", лекция 1, раздел 6) и определим остатки от деления на 3 чисел X^5 и Y^8. Для X^5 он будет равен 2, а для Y^7 - 0. Это означает, что и (8^5)%3=2 и (6^8)%3=0. В случае, если остатки от деления не 3 не совпали, то и сами числа не могут совпасть (рассчитать вероятность совпадения чисел при совпадении остатков - задача сложная, но решаемая; для нас главное, что она отлична от нуля).
Проведя достаточное количество тестов (например, 1000 или 10000, сколько будет успевать программа) и получив совпадение остатков на них можно с большой долей уверенности сказать, что числа совпадают (ведь должны быть тесты, на которых ответ correct? :) ). Числа для тестов можно было выбирать как простые, так и просто случайные.
Увлекающиеся математикой могут оценить вероятность правильного ответа в зависимости от количества тестов.
Для реализации такого варианта решения нам необходимы были следующие реализованные функции:
1) Подсчет остатка от деления длинного числа на короткое
2) Деление длинного числа на 2
3) Вычитание из длинного числа 1
4) Быстрое возведение в степень по модулю