Плюсануть
Поделиться
Класснуть
Запинить

Задачи из рубрикатора

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

Условие задачи  
ID 37550: Папа и дочь
Папа и дочь
Темы: НОД и алгоритм Евклида   

Длина шага папы – А см, а у маленькой дочери – В см. Они начинают идти, поставив ноги на одну отметку. Какое расстояние они пройдут, чтобы их ноги опять встали вровень?

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

Примеры

Входные данные Выходные данные
1 70 15 210

ID 37553: Объем информации
Объем информации
Темы: НОД и алгоритм Евклида   

Студент на первом курсе скачивал из интернета в среднем А Кбайт информации в день, а на втором курсе – В Кбайт, оплачивая одну и ту же сумму денег за полученный интернетный трафик в неделю. Какой наименьший объем информации в Кбайтах он скачивал за неделю?

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

Примеры

Входные данные Выходные данные
1 60 75 300

ID 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).
 
Пример входных данных:
3
3 3 3
Пример выходных данных:
3

(c) Свиридов Я.

ID 18691: Короткий НОД
Короткий НОД
Темы: НОД и алгоритм Евклида   

Задача "Короткий НОД"
 
Даны два числа. Найти их наибольший общий делитель.
 
Входные данные
Вводятся два натуральных числа, не превышающих 30000.
 
Выходные данные
Выведите НОД введенных чисел
 
Пример входного файла
42 12
 
Пример выходного файла
6

ID 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 ≤ 109).
Выходные данные: Выведите два натуральных числа x и y (1 ≤ x ≤ y), таких, что НОД(a, b) = НОД(x, y), НОК(a, b) = НОК(x, y), а их разность y − x минимальна.

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

ID 37552: Орхидеи
Орхидеи
Темы: НОД и алгоритм Евклида   

В теплице посадили в 2 ряда разные сорта орхидей. Цветы одного сорта разместили на расстоянии А см между растениями, а другого - на В см. Через какое расстояние орхидеи обоих сортов окажутся рядом? 

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

Примеры

Входные данные Выходные данные
1 15 18 90

ID 34852: Длинный НОД
Длинный НОД
Темы: НОД и алгоритм Евклида   

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

Примеры
Входные данные Выходные данные
1 42 12 6

ID 30777: Апельсины
Апельсины
Темы: НОД и алгоритм Евклида   

Катя решила пригласить к себе в гости n друзей. Так как ее друзья очень любят фрукты, то в качестве угощения для них она купила m одинаковых апельсинов.
Она хочет разрезать каждый апельсин на одинаковое число равных долек так, чтобы их можно было распределить между гостями (сама Катя апельсины есть не будет), и всем гостям досталось поровну долек.
 
Напишите программу, которая вычисляет минимальное количество долек, на которое необходимо разрезать каждый апельсин, чтобы были выполнены указанные выше условия.
 
Входные данные: Входная строка содержит два положительных целых числа n и m (1 ≤ n, m ≤ 109).
Выходные данные Выведите ответ на задачу.

Примеры
Входные данные Выходные данные
1 2 5 2
2 2 4 1

ID 12483: Квадраты
Квадраты
Темы: НОД и алгоритм Евклида   

На уроке труда всем раздали по прямоугольнику со сторонами размером A и B (целые, 1 ≤ A, B ≤ 231 − 1). Мальчик Сеня очень любит резать прямоугольники с особым цинизмом, и когда учитель предлагает всем вырезать из прямоугольника квадраты, то Сеня поступает весьма хитроумно. Он одним разрезом, параллельным стороне прямоугольника, отсекает от прямоугольника квадрат со стороной, равной наименьшей стороне прямоугольника и продолжает проделывать эту же процедуру с оставшейся после разреза частью. Если часть оказывается квадратом, то Сеня успокаивается и принимается считать получившиеся квадраты.
Сколько же он нарежет квадратов?

Входные данные: Числа A и B, задаются в одной строке через пробел
Выходные данные:  Количество получившихся квадратов

Примеры

Входные данные Выходные данные
1 1 2 2

ID 31872: Сложить две дроби
Сложить две дроби
Темы: НОД и алгоритм Евклида   

Даны две рациональные дроби: a/b и c/d. Сложите их и результат представьте в виде несократимой дроби m/n.
 
Входные данные
Программа получает на вход 4 натуральных числа a, b, c, d, не превосходящих 100.
 
Выходные данные
Программа должна вывести 2 натуральных числа m и n такие, что m/n=a/b+c/d и дробь m/n – несократима.
 
Ввод Вывод
1 3 1 2 5 6

ID 18692: Длинный НОД
Длинный НОД
Темы: Рекурсия    НОД и алгоритм Евклида   

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

Примеры
Входные данные Выходные данные
1 42 12 6

ID 29423: Сокращение дроби
Сокращение дроби
Темы: НОД и алгоритм Евклида   

Дана дробь a/b. Требуется ее сократить, то есть записать это же число в виде c/d, где c — целое число, d — натуральное число и d минимальное возможное.
 
Входные данные
Вводятся два целых числа a и b (–100≤a≤100, 0<b≤100).
 
Выходные данные
Выведите два числа c и d.
 
Ввод Вывод
3 6 1 2
-2 5 -2 5

ID 12482: Упорядоченные дроби
Упорядоченные дроби
Темы: НОД и алгоритм Евклида   

Вывести в порядке возрастания все несократимые дроби, заключённые между 0 и 1, знаменатели которых не превышают N.
Входные данные: В первой строке находится единственное число N (2 ≤ N ≤ 255).
Выходные данные: В каждой строке выводится дробь.

Примеры
Входные данные Выходные данные
1 5 1/5
1/4
1/3
2/5
1/2
3/5
2/3
3/4
4/5

 

ID 30770: Единичный НОД
Единичный НОД
Темы: НОД и алгоритм Евклида   

Заданы два натуральных числа в десятичной системе счисления, состоящие из единиц. В первом числе ровно N единиц, а во втором их ровно M. Требуется найти НОД этих чисел.
Напомним, что НОД (наибольший общий делитель) двух чисел a и b — это такое максимальное число c, что b делится на c и a делится на c.
 
Входные данные: В единственной строке  записаны два целых числа N и M (1 ≤ N, M ≤ 2000).
Выходные данные: Выведите ответ без ведущих нулей.

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

ID 37551: Математический конкурс
Математический конкурс
Темы: НОД и алгоритм Евклида   

На математическом конкурсе ребята играли в увлекательную древнюю китайскую головоломку Танграм. В одном игровом комплекте было А остроугольных, а в другом - В тупоугольных треугольников. Какое наименьшее число участников могут пользоваться комплектами из одинакового количества каждого вида треугольников?

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

Примеры

Входные данные Выходные данные
1 12 15 60

ID 37554: Вьетнамские умельцы
Вьетнамские умельцы
Темы: НОД и алгоритм Евклида   

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

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

Примеры

Входные данные Выходные данные
1 20 27 540