Арифметика

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

int gcd(int a, int b)
{
    if (b == 0)
    {
        return a;
    }
    else
    {
        return gcd(b, a % b);
    }
}

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

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

12
33

3

B: Бинарный алгоритм Евклида

В бинарном алгоритме Евклида не используются операции деления и остатка, а используется только проверка на чётность и деление на 2. Идея бинарного алгоритма Евклида следующая:
\(НОД(a,b)=2НОД(a/2,b/2)\), если \(a\) и \(b\) четные,
\(НОД(a,b)=НОД(a/2,b)\), если \(a\) четное, \(b\) нечетное,
\(НОД(a,b)=НОД(a,b/2)\), если \(a\) нечетное, \(b\) четное,
\(НОД(a,b)=НОД(a-b,b)\), если \(a\) и \(b\) нечетные, \(a\ge b\).

Реализуйте бинарный алгоритм Евклида для вычисления НОД двух чисел.

12
33

3

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

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

4

2 2

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

Дано натуральное число \(N\) (\(2\le N \lt 2^{31}\)). Выведите все его простые натуральные делители в порядке неубывания с учетом кратности. Алгоритм должен иметь сложность \(O(\sqrt{n})\).

132

2 2 3 11

2

2

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

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

Программа получает на вход четыре числа \(a\), \(b\), \(c\), \(d\). Числа — целые, не превосходят по модулю 10000, \(b\ne0\), \(d\ne0\).

Программа должна вывести ответ в виде смешанной дроби. Если целая часть смешанной дроби равна 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: Сумма двух квадратов

Дано натуральное число \(N\) (\(1\le N \lt 2^{31}\)). Определите, можно ли его представить в виде суммы двух точных натуральных квадратов.

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

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

20

2 4

21

Impossible

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

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

7

2 1 1 1

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

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

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

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

2

13

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

Определите const int N = 10000000 и создайте массив bool IsPrime[N]. Заполните его нулями и единичками так, чтобы IsPrime[i] == 1, если i - простое число и IsPrime[i] == 0, если i — составное.

Для этого сначала заполняем массив единицами. Затем “вычеркиваем” (то есть помечаем нулями) те элементы, которые делятся на 2, начиная с 4. Затем вычеркиваем те элементы, которые делятся на 3, начиная с 9. Затем вычеркиваем элементы, которые делятся на 5, начиная с 25... И так далее - находим следующее невычеркнутое число p и вычеркиваем все кратные p начиная с p².

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

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

5

11

J: Треугольник Паскаля

По данному числ \(N\) выведите первые \(N + 1\) строку треугольника Паскаля. Числа в строке разделяйте одним пробелом.

4

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1

Указание. Стройте строки треугольника Паскаля последовательно. Заведите два массива: для хранения последней построенной строки треугольника Паскаля и следующей за ней.

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

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

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

5

1/5
1/4
1/3
2/5
1/2
3/5
2/3
3/4
4/5

L: Отрезок

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

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

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

0 0 6 4

8

3 3 -3 3

0

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

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

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

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

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

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

6

prime

4

single
2 2

180

many
90 2
6 30

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

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

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

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

2

2 3

6

4 12

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

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

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

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

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

40

3 4 5
5 12 13
7 24 25
8 15 17
12 35 37
20 21 29

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

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

3
5

1 -3 2

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

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

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

1 2 3

1 1

10 6 8

2 -2

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

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

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

2 3

2

5 25

0

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

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

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

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

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

10

4

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

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

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

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

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

300

220 284

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

Имеется неограниченное количество монет в 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

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

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

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

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

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

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

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

4

2

5

4

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

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

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

Пример

54
60

3

3
7

-1

ZZ: Делимость степени - 2

Решите предыдущую задачу в ограничениях \((2\le A, B\le 10^{12})\).