2025/26, 9-профиль, C++, Теория чисел

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

12
33

3

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

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

12
33

3

Даны две дроби \(\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

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

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

0 0 6 4

8

3 3 -3 3

0

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

3
5

1 2 -1

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

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

2 3

2

5 25

0

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

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

1 2 3

1 1

10 6 8

2 -2

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

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

4

2 2

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

132

2 2 3 11

2

2

Определите 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\), начиная с \(p^2\).

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

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

5

11

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

чётное натуральное число \(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\) обозначается \(\tau(n)\).

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

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

2

2

6

4

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

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

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

2

3

6

12

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

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

300

220 284

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

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

4

2

5

4