Арифметика

Никакой новой теории. Вспомним только алгоритм Евклида:

def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)

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

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

12
33

3

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

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

4

2 2

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

Дано натуральное число N>1. Выведите все его простые натуральные делители с учетом кратности. Алгоритм должен иметь сложность O(sqrt(N)).

132

2 2 3 11

2

2

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

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

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

1 2 1 3

5/6

1 2 2 3

1 1/6

3 2 2 4

2

2 1 -4 2

0

-1 2 -1 3

-5/6

-1 2 -2 3

-1 1/6

3 10 -1 10

1/5

F: Отрезок

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

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

Тесты к этой задаче закрытые.

0 0 6 4

8

3 3 -3 3

0

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

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

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

Решение должно иметь сложность O(sqrt(N)).

20

2 4

21

Impossible

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

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

7

2 1 1 1

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

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

3
5

1 -3 2

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

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

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

1 2 3

1 1

10 6 8

2 -2

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

Пусть дано числа a и n. Обратным элементом к числу a в кольце вычетов по модулю n называется такое число b, что ab === 1 (mod n), то есть ab дает остаток 1 при делении на n.

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

2 3

2

5 25

0

L: Числовые функции

Количество всех натуральных делителей натурального числа n обозначим T(n). Сумма всех натуральных делителей числа n обозначим S(n).

Дано натуральное n ≤ 10⁹. Вычислите T(n) и S(n).

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

2

2 3

6

4 12

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

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

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

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

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

10

4

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

Решите предыдущую задачу в ограничениях n ≤ 10⁸. Такое решение оценивалось в 60 баллов из 100.

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

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

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

300

220 284

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

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

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

2

2

5

4

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

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

Тесты к этой задаче закрытые.

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

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

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

Тесты к этой задаче закрытые.

2

13

S: Исполнитель “Водолей”

У исполнителя “Водолей” есть два сосуда, первый объемом 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⁵ операций.

Тесты к этой задаче закрытые.

3 5 1

>A
A>B
>A
A>B

3 5 100

Impossible