Элементарная теория чисел

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

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

В задачах этого листка следует использовать тип данных long long.

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\). Числа — целые, не превосходят по модулю \(10^9\), \(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: Отрезок

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

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

Ввод Вывод
0 0 6 4
8
3 3 -3 3
0

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

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

Ввод Вывод
3
5
1 -3 2

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

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

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

Ввод Вывод
5
1/5
1/4
1/3
2/5
1/2
3/5
2/3
3/4
4/5

I: Делители - 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

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

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

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

Ввод Вывод
2 3
2
5 25
0

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

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

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

Ввод Вывод
1 2 3
1 1
10 6 8
2 -2

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, не превосходящих 104 Вам необходимо вывести алгоритм действий Водолея, который позволяет получить в точности N литров в одном из сосудов, если же такого алгоритма не существует, то программа должна вывести текст Impossible.

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

Ввод Вывод
3 5 1
>A
A>B
>A
A>B
3 5 100
Impossible

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

Определите const int N = 100000000 (\(10^8\)) и создайте массив vector<bool> is_prime(n + 1, true). Заполните его значениями так, чтобы is_prime[i] == true, если i — простое число и is_prime[i] == false, если i — составное.

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

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

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

Ввод Вывод
5
11

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

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

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

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

Ввод Вывод
20
2 4
21
Impossible

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

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

Ввод Вывод
7
2 1 1 1

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

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

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

Ввод Вывод
2
13

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

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

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

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

Ввод Вывод
2
2
6
4

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

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

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

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

Ввод Вывод
2
3
6
12

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

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

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

Ввод Вывод
300
220 284

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

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

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

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

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

Ввод Вывод
4
2
5
4

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

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

Четное натуральное число \(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

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

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

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

Пример

Ввод Вывод
54
60
3
3
7
-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\) (т.е. числа в тройке упорядочены по возрастанию). Сами тройки должны быть упорядочены в лексикографическом порядке.

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

Ввод Вывод
40
3 4 5
5 12 13
7 24 25
8 15 17
12 35 37
20 21 29

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

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

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

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