НОД и алгоритм Евклида

25 задачвместе с подтемами
Число у задачи — рейтинг сложности, слово рядом — насколько она трудна по сравнению с другими задачами такого же типа. Шкалы задач с ответом и задач с кодом между собой не сравниваются. Рядом — счётчики попыток: ✓ успешные, ✗ неуспешные.
РейтингЛюбойдо 800800–11991200–15991600+Без рейтинга
СначалаПодходящиеНовыеПопулярныеПростыеСложные
Расклейка афиш#50925

С утра по Васюкам ходил высокий худой старик в золотом пенсне и в коротких, очень грязных, испачканных клеевыми красками сапогах. Он наклеивал на стены рукописные афиши.

И.Ильф, Е.Петров. <<Двенадцать стульев>>.

Ипполит Матвеевич Воробьянинов ходит вдоль улицы из \(n\) домов, пронумерованных числами от \(1\) до \(n\), и расклеивает афиши. Сначала он наклеил афиши на каждый дом, номер которого делился без остатка на \(a\). Поскольку афиш осталось еще много, вторым проходом он наклеил афиши на каждый дом, номер которого делился без остатка на \(b\). При этом, если на доме уже была наклеена афиша, новую Воробьянинов не клеил. Сколько всего афиш расклеил бывший предводитель дворянства?

Формат входных данных
Три строки содержат три натуральных числа: \(n\) — количество домов на улице, \(a\) и \(b\) — выбранные Воробьяниновым числа. Все числа не превосходят \(10^9\).

Формат выходных данных
Выведите одно неотрицательное целое число — количество расклеенных афиш.

Замечание
В первом примере на улице \(10\) домов. Ипполит Матвеевич первым проходом расклеил пять афиш на дома, номера которых делятся на \(2\), то есть на дома с номерами \(2\), \(4\), \(6\), \(8\), \(10\). Вторым проходом он расклеил две афиши на дома, номера которых делятся на \(3\), то есть на дома с номерами \(3\) и \(9\). Дом номер \(6\) он пропустил — на нем афиша уже висит. Всего наклеено \(7\) афиш.

Во втором примере Воробьянинов не наклеит ни одной афиши.

Вывод формулыНОД и алгоритм Евклида
✓ 23✗ 91700средняяВойти и решать
Прогулка Громозеки и Алисы#39392
Громозека и Алиса старые друзья. Встречаясь на какой-то планете, они постоянно заходят в кафе. Но Алиса не любит заходить в каждое a-ое кафе, а Громозека в каждое g-ое кафе. Чтобы никого не обидеть, они не заходят в те кафе, в которые не хотят заходить одновременно и Алиса и Громозека. На очередной прогулке у них на пути N кафе. Во сколько кафе они смогут зайти?

Входные данные
Единственная строка содержит три целых числа - a , g , N ( 1 <= a , g , N <= 109 ).

Выходные данные
Выведите единственное число - количество кафе, в которые смогут зайти Громозека и Алиса.
 
Примеры
№ Входные данные Выходные данные
1 1 1 10 0
2 1 2 5 3
АлгоритмыНОД и алгоритм Евклида
✓ 308✗ 900500лёгкаяВойти и решать
Кинотеатр#38847
Марья Ивановна с Марьей Михайловной привели школьников в кинотеатр. Чтобы не было никаких обид, Марья Ивановна построила всех школьников по алфавиту и рассадила их: сначала в первый ряд слева направо, затем во второй слева направо и т.д., заполнив весь зал из n рядов по m кресел. Тут пришла Марья Михайловна и сказала, что ребята сели неправильно – надо пересесть. Она предложила сначала заполнить все первые места от первого ряда к последнему, затем все вторые места и т. д.

Определите, сколько школьников после такой пересадки останется на своем месте.

Например, если n = 3 и m = 3, то в первом случае дети сядут так:

1    2    3
4    5    6
7    8    9
а во втором – так:
1    4    7
2    5    8
3    6    9
Таким образом, три школьника: 1, 5 и 9 останутся на своих местах.

Входные данные
Вводятся два целых числа n и m (1 ≤ n, m ≤ 109 ).

Выходные данные
Выведите количество школьников, которые останутся на своих местах.
 
Примеры
№ Входные данные Выходные данные
1 3 3 3
2 2 4 2
НОД и алгоритм Евклида
✓ 170✗ 335600лёгкаяВойти и решать
Много часов#38584
У Громозеки есть N часов. Стрелка i-х часов (\(1<=i<=N\)) поворачивается на 360 ° ровно за Ti секунд. Изначально стрелка всех часов стоит на месте и направлена прямо вверх. Громозека запускает все часы одновременно. Через сколько секунд стрелка всех часов снова укажет прямо вверх?

Входные данные
В первой строке записано целое число N (\(1<=N<=100\)). В следующих N строках записаны целые числа Ti (\(1<=T_i<=10^{18}\)), по одному числу в строке. 

Выходные данные
Выведите на экран ответ. Гарантируется, что ответ не превышает \(10^{18}\).
 

 

Примеры
№ Входные данные Выходные данные Пояснение
1 2
2
3		 6 У нас есть двое часов. Время, когда стрелка каждых часов указывает вверх, выглядит следующим образом:
Часы 1: 2, 4, 6, ... секунд после начала.
Часы 2: 3, 6, 9, ... секунд после начала.
Таким образом, требуется 6 секунд, пока стрелки обоих часов снова не укажут прямо вверх.
2 5
2
5
10
1000000000000000000
1000000000000000000		 1000000000000000000  

 

НОД и алгоритм Евклида
✓ 188✗ 336600лёгкаяВойти и решать
Отрезок_0#38323
На клетчатой бумаге Петя нарисовал отрезок из точки с координатами (a,b) в точку с координатами (c,d). Через сколько клеток проходит этот отрезок (считается, что отрезок проходит через клетку, если он проходит через ее внутренность, если же он проходит только через вершину или по границе клетки, считается, что он не проходит через клетку).

Входные данные
Вводятся целые числа a, b, c, d. Числа по модулю не превышают 109.

Выходные данные
Выведите одно число — количество клеток, через которые проходит отрезок.
Примеры
№ Входные данные Выходные данные
1 0 0 6 4 8
2 3 3 -3 3 0
НОД и алгоритм Евклида
✓ 211✗ 188600лёгкаяВойти и решать
Автобусы#38300
В Берляндии плачевная ситуация с междугородним автобусным сообщением. Во всей стране есть всего три автобусных маршрута, по каждому из которых курсирует лишь один автобус. В первый день нового года ровно в полночь все три автобуса отправляются по своим маршрутам из столицы Берляндии. Известно, что первому автобусу на то, чтобы проехать весь маршрут и вернуться в столицу требуется a минут, второму — b минут, а третьему — c минут. Таким образом, первый автобус отправляется из столицы Берляндии в моменты времени 0, a, 2a, 3a , второй — в моменты времени 0, b, 2b, 3b , а третий в моменты времени 0, c, 2c, 3c .

Момент времени называется подходящим для пересадки , если в этот момент все три автобуса отправляются из столицы Берляндии. Например если a=1, b=2, c=1, то моменты времени 0 и 2 являются подходящими для пересадки, а момент времени 1 не является, потому что в этот момент времени второй автобус находится в пути. Берляндия — особая страна с особым измерением времени, поэтому в берляндских сутках ровно t минут. Это означает, что в первый день происходят все моменты времени с 0-го по (t−1)-й включительно, во второй день — c t-го по (2t−1)-й включительно, в третий — с 2t-го по (3t−1)-й включительно и так далее.

Министерство транспорта Берляндии заинтересовалось, сколько подходящих для пересадки моментов времени произойдёт в d-й день в Берляндии. К сожалению, местные чиновники заняты другими делами, поэтому ответить на этот вопрос было поручено вам.

Входные данные
В пяти строках заданы пять целых чисел a, b, c, t  и d (1≤a, b, c≤106 , 1≤t, d≤109 ) — время полного прохождения маршрута первым, вторым и третьим автобусами, соответственно, количество минут в сутках и номер дня, которым интересуется министерство транспорта Берляндии.

Выходные данные
Выведите одно целое число — количество подходящих для пересадки моментов времени в d-й день.
Примеры
№ Входные данные Выходные данные Пояснения
1 1
2
1
3
1		 2 Сутки длятся 3 минуты, поэтому все моменты времени в день с номером 1 — это 0, 1, 2, из них моменты времени 0 и 2 являются подходящими для пересадки
2 2
3
4
7
2		 1 Здесь рассматриваются вторые сутки с моментами времени 7, 8, 9, 10, 11, 12, 13. Первый автобус отправляется в моменты времени 8, 10, 12, второй автобус — в моменты времени 9 и 12, а третий — в моменты времени 8 и 12. Таким образом, только момент времени 12 является подходящим для пересадки.
3 2
3
4
3
3		 0 Нет ни одного подходящего для пересадки момента времени
НОД и алгоритм Евклида
✓ 117✗ 327700средняяВойти и решать
Тушенка#38258
Приближалось лето, и Игорь, Гена и Денис решили пойти вместе в поход, как и в прошлом году. Почти все вопросы уже были решены: уже был проработан маршрут, куплены билеты на поезд, в шкафу у Дениса найдена четырехместная палатка, а под кроватью у Игоря — топор. Осталось решить только вопрос с продуктами.

В прошлом году ребята честно признались, что не знают, сколько им нужно продуктов, и попросили помочь свою одноклассницу Настю, которая составила им список покупок. Но в этом году снова спрашивать у нее уже как-то несолидно. Можно было бы посмотреть, сколько они покупали в прошлом году, и взять столько же, но ни у кого из ребят не сохранилось ни чеков, ни списка продуктов.

Зато у них сохранилась переписка в социальной сети, где они спорили, кто сколько банок тушенки понесет. В этой переписке Игорь сначала предложил поделить всю тушенку в отношении a: b: c, так, что первую часть понесет сам Игорь, вторую — Гена, а третью — Денис. Но Денису это не понравилось, и он предложил поменять соотношение на d: e: f.

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

По данным двум отношениям a: b: c и d: e: f вычислите, сколько банок тушенки ребята покупали для прошлогоднего похода. Из всех возможных ответов выведите минимальный. Ребята помнят, что как минимум одна банка тушенки у них точно была.

Входные данные
В первой строке даны три целых положительных числа a, b, c, разделенные пробелами. Во второй строке даны три целых положительных числа d, e, f, также разделенные пробелами.

Все числа не превышают 1000.

Выходные данные
Выведите целое положительное число — количество банок тушенки.
 
Примеры
№ Входные данные Выходные данные Пояснения
1 10 3 7
3 1 1		 20 При делении тушенки между ребятами в отношении 10:3:7 Игорь понесет 10 банок, Гена — 3 банки, а Денис — 7 банок. А в случае соотношения 3:1:1 Игорю достанется 12 банок, а Гене и Денису по 4.
НОД и алгоритм Евклида
✓ 248✗ 862600лёгкаяВойти и решать
Треугольник Пети#37558

Пятиклассник Петя любит решать различные математические задачи. Последняя его задача заключалась в том, чтобы по целым числам a, b, найти такие целые x и y, которые бы помогли построить треугольник ABC  минимальной (ненулевой) площади. Треугольник Пети должен иметь следующие координаты \(A = (0, 0)\), \(B = (a, b)\), \(C = (x, y)\).
Помогите ему определить какую минимальную площадь может иметь треугольник ABC?

Входные данные
Даны два целых числа a и b, по модулю не превосходящие 109 (\(a^2 + b^2 > 0\)).

Выходные данные
Выведите одно число - минимальную возможную площадь треугольника ABC с точностью 10 - 6. 
 
Примеры
№ Входные данные Выходные данные
1 4 0 2.0
НОД и алгоритм Евклида
✓ 353✗ 642700средняяВойти и решать
Вьетнамские умельцы#37554
Вьетнамские народные умельцы из кусочков рисовой соломки делают декоративные панно, наклеивая их на досточки. Какой наименьшей длины (в мм) должна быть соломка, чтобы ее можно было разрезать на равные части по А мм и В мм, не получая обрезков?

Оформите решение задачи в виде функции solve(A, B), которая возвращает ответ. Ничего вводить и выводить Вам не нужно!

Примеры
№ Входные данные Выходные данные
1 20 27 540
НОД и алгоритм Евклида
✓ 62✗ 236500лёгкаяВойти и решать
Объем информации#37553
Студент на первом курсе скачивал из интернета в среднем А Кбайт информации в день, а на втором курсе – В Кбайт, оплачивая одну и ту же сумму денег за полученный интернетный трафик в неделю. Какой наименьший объем информации в Кбайтах он скачивал за неделю?

Оформите решение задачи в виде функции solve(A, B), которая возвращает ответ. Ничего вводить и выводить Вам не нужно!

Примеры
№ Входные данные Выходные данные
1 60 75 300
НОД и алгоритм Евклида
✓ 42✗ 212700средняяВойти и решать
Орхидеи#37552
В теплице посадили в 2 ряда разные сорта орхидей. Цветы одного сорта разместили на расстоянии А см между растениями, а другого - на В см. Через какое расстояние орхидеи обоих сортов окажутся рядом? 

Оформите решение задачи в виде функции solve(A, B), которая возвращает ответ. Ничего вводить и выводить Вам не нужно!

Примеры
№ Входные данные Выходные данные
1 15 18 90
НОД и алгоритм Евклида
✓ 36✗ 92500лёгкаяВойти и решать
Математический конкурс#37551
На математическом конкурсе ребята играли в увлекательную древнюю китайскую головоломку Танграм. В одном игровом комплекте было А остроугольных, а в другом - В тупоугольных треугольников. Какое наименьшее число участников могут пользоваться комплектами из одинакового количества каждого вида треугольников?

Оформите решение задачи в виде функции solve(A, B), которая возвращает ответ. Ничего вводить и выводить Вам не нужно!

Примеры
№ Входные данные Выходные данные
1 12 15 60
НОД и алгоритм Евклида
✓ 16✗ 21600лёгкаяВойти и решать
Папа и дочь#37550
Длина шага папы – А см, а у маленькой дочери – В см. Они начинают идти, поставив ноги на одну отметку. Какое расстояние они пройдут, чтобы их ноги опять встали вровень?

Оформите решение задачи в виде функции solve(A, B), которая возвращает ответ. Ничего вводить и выводить Вам не нужно!

Примеры
№ Входные данные Выходные данные
1 70 15 210
НОД и алгоритм Евклида
✓ 48✗ 117600лёгкаяВойти и решать
Длинный НОД#34852
Даны два числа. Найти их наибольший общий делитель.
 
Входные данные 
Вводятся два натуральных числа, не превышающих 109.

Выходные данные 
Выведите НОД введенных чисел.
 

Примеры
№ Входные данные Выходные данные
1 42 12 6
НОД и алгоритм Евклида
✓ 1 102✗ 781200лёгкаяВойти и решать
Расширенный алгоритм Евклида#31903
Даны натуральные числа \(a, b, c.\) Если уравнение \(a \cdot x + b \cdot y = c\) имеет решения в целых числах, то выведите через пробел \(НОД(a,b)\), \(x\) и \(y\) (какое-нибудь решение). Если решения не существует, то выведите слово Impossible.
 
Входные данные 
Натуральные числа и не превышают по модулю 10000.

Выходные данные 
Выведите ответ на задачу.
 
Примеры
№ Входные данные Выходные данные
1 1 2 3 1 1 1
2 10 6 8 2 2 -2
Расширенный алгоритм Евклида
✓ 402✗ 990600лёгкаяВойти и решать
Сложить две дроби#31872
Даны две рациональные дроби: \(a \over b\) и \(c \over d\). Сложите их и результат представьте в виде несократимой дроби \(m \over n\).
 
Входные данные 
Программа получает на вход 4 натуральных числа a, b, c, d, не превосходящих 100.
 
Выходные данные 
Программа должна вывести 2 натуральных числа m и n такие, что \({m \over n} = {a \over b}+ {c \over d}\) и дробь \(m \over n\) – несократима.
 
Примеры
№ Входные данные Выходные данные
1  1 3 1 2 5 6
НОД и алгоритм Евклида
✓ 1 117✗ 1 718400лёгкаяВойти и решать
Апельсины#30777
Катя решила пригласить к себе в гости n друзей. Так как ее друзья очень любят фрукты, то в качестве угощения для них она купила m одинаковых апельсинов. Она хочет разрезать каждый апельсин на одинаковое число равных долек так, чтобы их можно было распределить между гостями (сама Катя апельсины есть не будет), и всем досталось одинаковое количество долек.

Напишите программу, которая вычисляет минимальное количество долек, на которое необходимо разрезать каждый апельсин, чтобы были выполнены указанные выше условия.
 
Входные данные 
Входная строка содержит два положительных целых числа n и m (\(1 <= n, m <= 10^9\)).

Выходные данные 
Выведите ответ на задачу.
 
Примеры
№ Входные данные Выходные данные
1 2 5 2
2 2 4 1
НОД и алгоритм Евклида
✓ 778✗ 1 703500лёгкаяВойти и решать
Единичный НОД#30770
Заданы два натуральных числа в десятичной системе счисления, состоящие из единиц. В первом числе ровно N единиц, а во втором их ровно M. Требуется найти НОД этих чисел. 
 
Входные данные
В единственной строке  записаны два целых числа N и M (\(1 <= N,\ M <= 2000\)).
 
Выходные данные
Выведите ответ без ведущих нулей.
 

 

Примеры
№ Входные данные Выходные данные
1 1 1 1
2 1 2 1
НОД и алгоритм Евклида
✓ 370✗ 477500лёгкаяВойти и решать
Сокращение дроби#29423
Дана дробь \(a \over b\). Требуется ее сократить, то есть записать это же число в виде \(c \over d\), где c — целое число, d - натуральное число и d минимальное возможное.
 
Входные данные 
Вводятся два целых числа a и b (\(-100<=a<=100,\ 0<b<=100\)).

Выходные данные 
Выведите два числа c и d.
 
Примеры
№ Входные данные Выходные данные
1 3 6  1 2
2 -2 5 -2 5
НОД и алгоритм Евклида
✓ 1 330✗ 3 699400лёгкаяВойти и решать
НОД и НОК#24905

Дано число n – количество чисел. В следующей строке дано n чисел, каждое не больше 1000.
Вам необходимо вывести количество таких пар чисел (a, b), что НОК (a, b) = НОД (a, b).

НОК (a, b) - наименьшее общее кратное этих двух чисел, то есть наименьшее число, которое делится сразу на оба числа. \( НОК (20, 30) = 60\).
НОД (a, b) – наибольший общий делитель этих двух чисел, то есть наибольшее число, на которое делятся оба числа. \(НОД (20, 30) = 10\).
Напишите эффективную по памяти и времени программу.

Входные данные
В первой строке вводится натуральное число n – количество данных вам чисел.
Во второй строке вводятся сами числа, каждое из них целое и принадлежит отрезку [0; 1000].
 
Выходные данные
Выведите одно целое число – количество пар чисел (a, b), таких, что НОК(a,b) = НОД(a,b).
 

 

Примеры
№ Входные данные Выходные данные
1 3
3 3 3		 3

 

НОД и алгоритм Евклида
✓ 636✗ 2 555600лёгкаяВойти и решать
Поделиться
Класснуть