Портал обучения информатике. Подготовка к ЕГЭ, ОГЭ, олимпиадам

Треугольник Пети#37558

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

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

Выходные данные
Выведите одно число - минимальную возможную площадь треугольника ABC с точностью 10^- 6.

Примеры

№	Входные данные	Выходные данные
1	4 0	2.0

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

✓ 353✗ 642700средняяВойти и решать

Задача для Пети и Вани#37555

Пятиклассники Петя и Ваня изучили на уроках математики следующий алгоритм Евклида:

Пусть a, b — числа, НОД которых надо найти.
Если b = 0, то число a — искомый НОД.
Если b > a, то необходимо поменять местами числа a и b.
Присвоить числу a значение a – b.
Вернуться к шагу 2.

Маша придумала для них задачу на закрепление. Она попросила мальчиков придумать такие числа a, b, c и d, что в процессе реализации алгоритма Евклида для заданной пары чисел (a, b) наступает такой момент, когда перед исполнением шага 2 число a будет равно c, а число b будет равно d.

Напишите для Маши программу, которая проверит, удовлетворяют ли числа a, b, c, d условиям Маши.

Входные данные: Первая строка входных данных содержит количество наборов входных данных K (\(1 <= K <= 100\)). Далее идут описания этих наборов. Каждое описание состоит из двух строк. Первая из них содержит два целых числа: a, b (\(1 <= a,\ b <= 10^{18}\)). Вторая строка – два целых числа: c, d (\(1 <= c,\ d <= 10^{18}\)).
Все числа в строках разделены пробелом.

Выходные данные: Для каждого набора входных данных выведите слово «YES», если в процессе применения алгоритма Евклида к паре чисел (a, b) в какой-то момент получается пара (c, d). В противном случае выведите слово «NO».

Примеры

№	Входные данные	Выходные данные
1	2 20 10 10 10 10 7 2 4	YES NO

Вывод формулы НОД и алгоритм Евклида

✓ 106✗ 1 7501 000средняяВойти и решать

Вьетнамские умельцы#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

Даны два числа. Найти их наибольший общий делитель.

Входные данные
Вводятся два натуральных числа, не превышающих 10⁹.

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

Примеры

№	Входные данные	Выходные данные
1	42 12	6

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

✓ 1 102✗ 781200лёгкаяВойти и решать

Диофантовы уравнения#33656

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

Входные данные
Вводятся три натуральных числа.

Выходные данные
Выведите ответ на задачу.

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

Примеры

№	Входные данные	Выходные данные
1	1 2 3	1 1
2	10 6 8	2 -2

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

✓ 170✗ 1 153800средняяВойти и решать

RSA: Расшифровка#31923

Даны два простых числа p и q. Надо расшифровать сообщение состоящее из последовательности чисел, оканчивающееся нулем, с помощью алгоритма RSA.

Входные данные
В первой строке вводятся p и q (\(3<=p,q<10\)), далее вводится сообщение состоящее из натуральных чисел, каждое не превышающее 100. Сообщение заканчивается нулем.

Выходные данные
Выведите расшифрованное сообщение.

Примеры

№	Входные данные	Выходные данные
1	3 7 1 11 12 0	123

Быстрое возведение в степень МЦКО-10. RSA Расширенный алгоритм Евклида

✓ 6✗ 351 200средняяВойти и решать

Расширенный алгоритм Евклида#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лёгкаяВойти и решать

Рассадка зверей#24764

Сегодня Колобок созвал всех волков и лис к себе в гости на чаепитие. Чаепитие пройдет за круглым столом, за которым всего n мест. Колобок хочет рассадить зверей по-особенному — так, чтобы волки не сидели только с волками, а лисы только с лисами. Поэтому для каждого места он записал одно целое число — сколько лис должно сидеть на расстоянии не более d от этого места, включая это место.

Два места находятся на расстоянии не более d, если между ними встречаются не более d−1 места при движении по или против часовой стрелки от одного к другому. Таким образом, для заданного места всего существует 2d + 1 место, находящееся на расстоянии не более d от него.

Теперь он хочет придумать какую-нибудь рассадку зверей, удовлетворяющую этим ограничениям.

Входные данные
В первой строке находятся два натуральных числа n, d (3 ≤ n ≤ 10⁵ , 3 ≤ 2d+1 ≤ n) — количество мест за круглым столом и расстояние d. В следующей строке находятся n неотрицательных целых чисел ai (0 ≤ a_i ≤ 2d+1) — количество лис на расстоянии не более d от этого места, включая это место. Информация о местах перечислена в порядке их следования по кругу.

Выходные данные
Если решения не существует, выведите «NO», иначе в первой строке выведите «YES», а в следу- ющей n чисел: 1 в том случае, если на этом месте сидит лиса, и 0, если на этом месте сидит волк. Если ответов несколько, разрешается вывести любой.

Ввод	Вывод
5 1 2 2 1 2 2	YES 1 0 1 0 1
9 2 3 4 4 3 3 2 2 2 2	YES 1 0 1 1 1 0 0 0 1
6 1 3 3 3 3 3 1	NO

Дерево отрезков, RSQ, RMQ НОД и алгоритм Евклида

1 300средняяВойти и решать

НОД и НОК#21815

Сережа очень любит математические задачи. Недавно на математическом кружке ему рассказали, что такое НОД и НОК.

НОД двух натуральных чисел a и b — это их наибольший общий делитель, то есть такое максимальное число x, что a делится на x и b делится на x. Например, \(НОД(24, 18) = 6\). А НОК целых чисел a и b — это их наименьшее общее кратное, то есть такое минимальное число x, что x делится на a и x делится на b. Например, \(НОК(24, 18) = 72\).

Сережа сразу заметил, что может существовать несколько пар чисел с одинаковыми НОД и НОК. Теперь он заинтересовался вопросом: если заданы числа a и b, насколько близко друг к другу могут быть два числа, у которых такие же НОД и НОК.

Помогите ему по заданным двум числам a и b найти такие числа x и y, что \(НОД(a, b) = НОД(x, y)\), \(НОК(a, b) = НОК(x, y)\), а их разность \(y - x\) минимальна.

Входные данные
В первой строке входного файла находятся два натуральных числа a и b (\(1 <= a, b <= 10^9\)).

Выходные данные
Выведите два натуральных числа x и y (\(1 <= x <= y\)), таких, что \(НОД(a, b) = НОД(x, y)\), \(НОК(a, b) = НОК(x, y)\), а их разность \(y - x\) минимальна.

Примеры

№	Входные данные	Выходные данные
1	3 4	3 4

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

✓ 75✗ 1 0641 100средняяВойти и решать

Алгоритм Евклида#21722

Для быстрого вычисления наибольшего общего делителя двух чисел используют алгоритм Евклида. Он построен на следующем соотношении: НОД(a,b)=НОД(a % b,b). Реализуйте рекурсивный алгоритм Евклида в виде функции gcd(a, b).

Ввод
12 16
Вывод
4

НОД и алгоритм Евклида Рекурсия

✓ 71✗ 36500лёгкаяВойти и решать

Длинный НОД#18692

Даны два числа. Найти их наибольший общий делитель.

Входные данные: Вводятся два натуральных числа, не превышающих 10^9, (запись 10^9 обозначает "10 в 9-й степени", то есть 1000000000).

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

Примеры

№	Входные данные	Выходные данные
1	42 12	6

НОД и алгоритм Евклида Рекурсия

✓ 1 192✗ 2 048300лёгкаяВойти и решать