2025/26, Кружок для начинающих, Алгоритм Евклида

По данным натуральным числам n и m найдите их наибольший общий делитель.

1
1

1

2
1

1

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

1
1

1

2
1

1

Даны две сцепленные шестеренки. У одной шестеренки \(N\) зубцов, у другой – \(K\). Требуется найти, какое минимальное число поворотов на один зубчик требуется сделать, чтобы шестеренки вернулись в исходное состояние.

3 4

12

35867 1209

107601

Дано \(N\) чисел. Найти самое большое число, на которое делятся все \(N\) чисел.

1
9

9

2
90 35

5

Полоска бумаги имеет размеры \(A \times B\). Каждый раз от нее отрезается квадрат максимального размера до тех пор, пока не получится квадрат. Сколько квадратов получится?

15 3

5

12 8

3

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

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

Найдите наибольшую правильную несократимую дробь, у которой сумма числителя и знаменателя равна \(n\).

10

3 7

23

11 12

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

0 0 6 4

8

3 3 -3 3

0

Марья Ивановна с Марьей Михайловной привели школьников в кинотеатр. Чтобы не было никаких обид, Марья Ивановна построила всех школьников по алфавиту и рассадила их: сначала в первый ряд слева направо, затем во второй слева направо и т.д., заполнив весь зал из \(n\) рядов по \(m\) кресел. Тут пришла Марья Михайловна и сказала, что ребята сели неправильно – надо пересесть. Она предложила сначала заполнить все первые места от первого ряда к последнему, затем все вторые места и т. д.

3 3

3

2 4

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).

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

3 5 1

>A
A>B
>A
A>B

3 5 2

>A
A>B
>A
A>B
B>
A>B
>A
A>B
>A
A>B

Вам дан массив \(a\), состоящий из \(n\) целых чисел \(a_{1}, a_{2}, \ldots, a_{n}\).

Друзья попросили вас сделать \(\href {https://ru.wikipedia.org/wiki/Наибольший_общий_делитель} {наибольший общий делитель (НОД)}\) всех элементов массива равным \(1\).

За одну операцию вы можете сделать следующее:

\(.\) Выбрать произвольный индекс в массиве \(1 \leq i \leq n\);

\(.\) Сделать \(a_{i} = \gcd(a_i, i)\), где \(\gcd(x, y)\) обозначает НОД чисел \(x\) и \(y\). Стоимость такой операции равна \(n - i + 1\).

Вам нужно найти минимальную суммарную стоимость операций, которые нужно сделать, чтобы НОД всех элементов массива стал равен \(1\).

9
1
1
1
2
2
2 4
3
3 6 9
4
5 10 15 20
5
120 60 80 40 80
6
150 90 180 120 60 30
6
2 4 6 9 12 18
6
30 60 90 120 125 125

0
1
2
2
1
3
3
0
1