A: Алгоритм Евклида

Даны два натуральных числа. Вычислите их наибольший общий делитель при помощи алгоритма Евклида, реализованного без использования рекурсии.

B: Гипотеза Гольдбаха

Гипотеза Гольдбаха (недоказанная до сих пор) утверждает, что любое четное число (кроме 2) можно представить в виде суммы двух простых чисел. Дано натуральное четное число, большее 2, выведите два простых числа, дающих в сумме данное.

C: Разложение на множители

Дано натуральное число $N>1$. Постройте его разложение на простые множители. Решение должно быть оформлено в виде функции factor(n), возвращающей список делителей числа в порядке неубывания. Основная программа должна вызывать функцию factor и выводить возвращенный список функцией print.

D: Разложение на множители — 2

Дано натуральное число $N>1$. Постройте его каноническое разложение на простые множители. Решение должно быть оформлено в виде функции factor(n), возвращающей словарь, в котором ключи — простые делители числа, а значения — степени данного простого числа в каноническом разложении. Основная программа должна вызывать функцию Factor и выводить возвращенный словарь функцией print.

E: Сумма двух дробей

Даны две дроби $\frac ab$ и $\frac cd$ (числа $a$ и $c$ — целые, $b$ и $d$ — натуральные). Вычислите их сумму и запишите ее в виде смешанной дроби $x\frac yz$ (число $x$ целое, числа $y$ и $z$ натуральные, дробь $\frac yz$ — правильная несократимая).

Программа получает на вход четыре числа $a$, $b$, $c$, $d$ и должна вывести ответ в виде смешанной дроби. Если целая часть смешанной дроби равна 0, ее выводить не надо. Если дробная часть смешанной дроби равна 0, ее выводить не надо. Если число отрицательное, то перед ним выводится знак «-». Следуйте формату вывода, приведенному в примерах.

F: Отрезок

На клетчатой бумаге нарисовали отрезок из точки с координатами $(a,b)$ в точку с координатами $(c,d)$. Через сколько клеток проходит этот отрезок (считается, что отрезок проходит через клетку, если он проходит через ее внутренность, если же он проходит только через вершину или по границе клетки, считается, что он не проходит через клетку).

Программа получает на вход четыре числа: $a$, $b$, $c$, $d$.

G: Расширенный алгоритм Евклида

Даны два натуральных числа $a$ и $b$. Найдите их наибольший общий делитель $d$ и два таких целых числа $x$ и $y$, что $ax+by=d$. Программа должна вывести числа $d$, $x$, $y$.

H: Обратный элемент

Пусть даны числа $a$ и $n$. Обратным элементом к числу $a$ в кольце вычетов по модулю $n$ называется такое число $b$, что $ab\equiv 1 \pmod{n}$, то есть $ab$ дает остаток 1 при делении на $n$.

Даны числа $a$ и $n$. Выведите значение обратного элемента к числу $a$ в кольце вычетов по модулю $n$. Если обратного элемента не существует, выведите число 0.

I: Диофантово уравнение

Даны натуральные числа $a$, $b$, $c$. Если уравнение $ax+by=c$ имеет решения в целых числах, то выберите то решение, в котором число $x$ имеет наименьшее неотрицательное значение и выведите это решение (два числа $x$ и $y$ через один пробел). Если решения не существует, то выведите слово Impossible.

Сложность алгоритма должна быть равна сложности алгоритма Евклида + константа.

J: Упорядоченные дроби

Выведите в порядке возрастания все несократимые дроби, заключённые между 0 и 1, знаменатели которых не превышают N.

Программа получает на вход целое число $N\le20$ и выводит одну дробь в каждой строке.

K: Делители - 30

На региональном этапе Всероссийской олимпиаде школьников по информатике 23 января 2011 года предлагалась задача, условие которой в варианте на 30 баллов из 100 звучит так.

Дано натуральное число $n \le 1000$. Подсчитайте количество таких пар чисел $(a, b)$, что:

1. $a$ и $b$ — делители $n$.
2. $a < b$.
3. $a$ и $b$ — взаимно простые.
4. $ab\le n$.

Выведите количество таких пар.

L: Исполнитель «Водолей»

У исполнителя «Водолей» есть два сосуда, первый объемом A литров, второй объемом B литров, а также кран с водой. Водолей может выполнять следующие операции:

1. Наполнить сосуд A (обозначается >A).
2. Наполнить сосуд B (обозначается >B).
3. Вылить воду из сосуда A (обозначается A>).
4. Вылить воду из сосуда B (обозначается B>).
5. Перелить воду из сосуда A в сосуд B (обозначается как A>B).
6. Перелить воду из сосуда B в сосуд A (обозначается как B>A).

Команда переливания из одного сосуда в другой приводят к тому, что либо первый сосуд полностью опустошается, либо второй сосуд полностью наполняется.

Программа получает на вход три натуральных числа A, B, N, не превосходящих 10⁴ Вам необходимо вывести алгоритм действий Водолея, который позволяет получить в точности N литров в одном из сосудов, если же такого алгоритма не существует, то программа должна вывести текст Impossible.

Количество операций в алгоритме не должно превышать 10⁵. Гарантируется, что если задача имеет решение, то есть решение, которое содержит не более, чем 10⁵ операций.

M: Решето Эратосфена

Возьмие N = 100000 и создайте массив is_prime = [True] * (N + 1). Заполните его значениями так, чтобы is_prime[i] == True, если i — простое число и is_prime[i] == False, если i — составное.

Для этого сначала заполняем массив True. Затем «вычеркиваем» (то есть помечаем нулями) те элементы, которые делятся на 2, начиная с 4. Затем вычеркиваем те элементы, которые делятся на 3, начиная с 9. Затем вычеркиваем элементы, которые делятся на 5, начиная с 25... И так далее —находим следующее невычеркнутое число $p$ и вычеркиваем все кратные $p$ начиная с $p^2$.

В результате невычернутыми останутся только простые числа. Такая процедура называется «Решето Эратосфена».

Напишите программу, которая строит решето Эратосфена, потом считывает натуральное число n и выводит n-е по счету простое число. Гарантируется, что это число не превосходит N.

PS. Оказывается, такая реализация имеет асимптотику $O(n \log \log n)$.

PSS. Алгоритм можно заметно оптимизировать: например нет особого смысла хранить и проверять чётные числа.

N: Сумма двух квадратов

Дано натуральное число $N$. Определите, можно ли его представить в виде суммы двух точных натуральных квадратов.

Если число $N$ представимо в виде суммы двух натуральных квадратов, выведите два натуральных числа $a$ и $b$ таких, что $a^2+b^2=N$, иначе выведите строку Impossible.

Решение должно иметь сложность $O(\sqrt{n})$.

O: Теорема Лагранжа

Теорема Лагранжа утверждает, что любое натуральное число можно представить в виде суммы не более, чем четырех точных квадратов. По данному числy N выведите от 1 до 4 натуральных чисел, квадраты которых в сумме дают значение N.

P: Количество целочисленных точек в круге

Дано натуральное число $R\le 10^5$. Определите количество целочисленных точек, находящихся внутри и на границе круга радиуса $R$ с центром в начале координат.

Ограничение по времени на решение — 1 секунда, сложность алгоритма должна быть $O(R)$.

Q: Количество делителей

Количество всех натуральных делителей натурального числа $n$ обозначается $\tau(n)$.

Дано натуральное $n\le 10^9$. Вычислите $\tau(n)$.

Сложность алгоритма должна быть $O(\sqrt{n})$.

R: Сумма делителей

Сумма всех натуральных делителей числа $n$ обозначается $\sigma(n)$.

Дано натуральное $n\le 10^9$. Вычислите $\sigma(n)$.

Сложность алгоритма должна быть $O(\sqrt{n})$.

S: Фи-функция Эйлера

Дано натуральное число $n\le 10^9$, определите количество натуральных чисел, меньших $n$ и взаимно простых с $n$. Это число обозначается $\varphi(n)$ и называется фи-функцией Эйлера.

Сложность алгоритма должна быть $O(\sqrt{n})$.

T: Дружественные числа

Два различных числа $n$ и $m$ называются дружественными, если сумма делителей числа $n$ (включая 1, но исключая само $n$) равна числу $m$ и наоборот. Например, 220 и 284 – дружественные числа.

По данному числу $k$ выведите все пары дружественных чисел, каждое из которых не превосходит $k$. Пары необходимо выводить по одной в строке, разделяя числа в паре пробелом. Каждая пара должна быть выведена только один раз (перестановка чисел новую пару не дает).

U: Выдача сдачи

Имеется неограниченное количество монет в 1, 2, 5, 10 рублей. Определите, сколькими способами можно выдать сдачу в $n$ рублей. Например, 5 рублей можно выдать четырьмя способами: 5=2+2+1=2+1+1+1=1+1+1+1+1.

Программа получает на вход число $n$, не превышающее 100.

V: Разложение на четнопростые

В этой задаче рассматриваются только четные целые числа.

Четное натуральное число $n$ будем называть четнопростым числом, если его нельзя представить в виде произведения двух четных чисел. Например, числа 2 и 6 — четнопростые.

Очевидно, что каждое число либо является четнопростым, либо разлагается в произведение четнопростых. Но такое разложение на четнопростые не всегда единственно.

Дано четное натуральное $n\le 10^9$. Если это число — четнопростое, выведите слово prime. Если это число единственным образом разлагается в произведение двух и более четнопростых, то выведите слово single, а в следующей строке выведите разложение этого числа на четнопростые множители. Если число допускает несколько различных разложений на четнопростые, то выведите слово many, а в следующих двух строках выведите два каких-нибудь различных разложения числа на четнопростые множители.

Сложность алгоритма должна быть $O(\sqrt{n})$.

W: Делимость степени

Даны два натуральных числа $A$ и $B$ $(2\le A, B\le 2\times10^{12})$. Найдите такое минимальное натуральное $n$, что $B^n$ делится на $A$.

Программа получает на вход два числа $A$ и $B$ и выводит одно значение $n$. Если никакая степень числа $B$ не делится на $A$, то выведите число -1.

X: Пифагоровы тройки

Три натуральных числа $x$, $y$, $z$ называются пифагоровой тройкой, если $x^2 + y^2 = z^2$. Пифагорова тройка называется примитивной, если числа $x$, $y$, $z$ являются взаимно простыми.

По данному натуральному $N\le3\,000$ найдите все примитивные пифагоровы тройки, в которых все числа не превосходят $N$.

Программа должна вывести в каждой строке по три натуральных числа $x$, $y$, $z$, причем $x \lt y \lt z$ и $x ^ 2 + y ^ 2 = z ^ 2$ (т.е. числа в тройке упорядочены по возрастанию). Сами тройки должны быть упорядочены в лексикографическом порядке.

Для эффективного поиска примитивных пифагоровых троек прочтите статью в википедии.

Y: Делители - 60

Решите задачу K: Делители - 30 в ограничениях $n\le 10^8$. Такое решение оценивалось в 60 баллов из 100.

Z: Выдача сдачи - 2

Решите задачу U: Выдача сдачи в ограничениях $n\le 10^6$. Сложность алгоритма должна быть $O(n)$.

ZA: Решето Грайса и Мисра (David Gries, Jayadev Misra)

Оказывается, существует алгоритм, похожий на решето Эратосфена, который работает за время $O(n)$ (это не так уж ценно), но бонусом позволяет не только находить простые числа в диапазоне от $1$ до $n$, но и быстро раскладывать их на множители.

Итак, пусть дано натуральное число $n$. Вычислим для каждого числа $i$ на отрезке $[2, n]$ его минимальный простой делитель. Для удобства будем хранить минимальный делитель в массиве lsd (least simple divisor), причём начинаем с 0. Положим lsd[0] = lsd[1] = 0.

Используя заполненный массив lsd проверять простоту и раскладывать на множители очень просто. Если нам нужно разложить на множители число $x \le n$, то первый делитель — это просто lsd[x]. Оставшиеся делители получатся при разложении числа x//lsd[x].

Но как заполнить массив lsd за время $O(n)$? Это — непростая задача. В качестве подсказки отметим, что каждое число $x$ представляется в виде $x = lsd[x] \cdot y$, причём $lsd[y] \ge lsd[x]$ (то есть минимальный простой делитель у $y$ не меньше, чем у $x$).

На вход даётся число n. Выведите список lsd длиной n+1 такой, что lsd[0] = lsd[1] = 0, и lsd[i] — минимальный простой делитель числа i.

ZB: Потоковая факторизация

На вход даётся натуральное число N, не превосходящее 100000, затем N натуральных чисел, каждое из которых не превосходит 1000000. Выведите разложение каждого из этих чисел на простые множители (см. формат вывода).