Во какая штука у меня получилась…
Пример1:
Найти а и b, если известно, что НОД (а, b) = 971 , НОК (a, b) = 2913
1) Делим НОК на НОД => 2913 / 971 = 3
2) Делим то, что получилось в п.1 на последовательность от 1 до то, что получилось в п.1:
3/1 = 3
3/2 = 1.5
3/3 = 1
3) Выбираем те значения, которые поделились без остатка. Т.к. тут без остатка только 1 и 3 то их мы и возьмем.
4) Умножаем НОД на 1 и на 3 = > 971*1 = 971, 971*3 = 2913.
Ответ: а = 2913, b = 971.
Пример 2:
Найти а и b при НОД = 12 и НОК = 120
1) Делим НОК на НОД => 120 / 12 = 10
2) Делим то, что получилось в п.1 на последовательность от 1 до то, что получилось в п.1:
(из всех чисел выбираем только те, что делятся без остатка)
10/1 = 10
10/2 = 5
…
10/5 = 2
…
10/10 = 1
Так как у нас помимо 1 и 10 получилось еще 2 числа (5 и 2), то мы умнажаем НОД на 2 и 5 => 12*2 = 24, 12*5 = 60
Ответ: а = 24, b = 60.
Скажите пожалуйста, такой алгоритм рабочий ?
Помогаю со студенческими работами здесь
Подскажите где ошибка в нахождени НОД. Вводятся два числа a b и они должны лежать в промежутке d1 d2. с-НОД
#include "stdafx.h"
#include
#include
#include
#include
#include
#include // для system…
Даны 3 числа А,В,С. Найти их НОД!!!
Даны 3 числа А,В,С. Найти их НОД!!!
Даны 3 числа А,В,С. Найти их НОД!!!
Даны 3 числа А,В,С. Найти их НОД!!!
Даны числа, найти НОД
Даны натуральные числа n,m; найти НОД(n,m). Использовать программу, включающую рекурсивную…
Искать еще темы с ответами
Или воспользуйтесь поиском по форуму:
2
Светило науки — 4904 ответа — 55437 раз оказано помощи
Ответ:
В общем случае однозначно определить эти числа нельзя
Пошаговое объяснение:
Пусть наибольший общий делитель чисел a и b равен d, а наибольшее общее кратное равно l. Попробуем найти числа a и b, зная d и l.
d — делитель a и b, значит, существуют такие целые x и y, что a = xd, b = yd. При этом d — наибольший общий делитель, так что x и y взаимно просты, в противном случае общий делитель x и y можно быть бы включить в НОД, и НОД бы увеличился.
НОК при этом равен xyd: если в уме разложить a и b на простые множители, можно понять, что в НОК должны входить все множители d и дополнительно все множители x и y. Другой способ это понять — знание того, что всегда НОД(a, b) · НОК(a, b) = ab.
Опираясь на написанное выше, можно поступать так:
- Если l не делится на d, то условие противоречиво, никакие a и b не смогут иметь такие НОК и НОД
- Иначе делим l на d, результат — произведение x на y.
- Раскладываем xy на простые множители. Степень каждого простого числа можно «отдать» либо x, либо y — но только полностью, так как у x и y нет общих сомножителей
- Полученные x и y домножаем на d и получаем a и b.
Пример
Найдём все натуральные числа a, b, НОД которых равен 7 и НОК равен 84.
- 84 делится на 7, всё хорошо
- xy = 84 : 7 = 12
- xy = 12 = 2² · 3. Степени 2 и 3 можно внести в x (тогда x = 12, y = 1); 2 в x и 3 в y (x = 4, y = 3); 3 в x и 2 в y (x = 3, y = 4); 2 и 3 в y (x = 1, y = 12)
- Этим значениям (x, y) соответствуют пары (a, b): (12 · 7, 1 · 7) = (84, 7), (28, 21), (21, 28) и (7, 84)
-
- 0
-
Как найти два числа, если известно их НОД и НОК?
Дана следующая информация. НОД = 20, НОК = 720. Необходимо найти пару чисел (a и b), которым подойдут данные значения НОД и НОК.
Прошерстил немалое кол-во информации в интернете, но так и не нашёл толкового алгоритма решения. Даже зная что a*b = НОД * НОК, к решению прийти особо не удаётся.
Если можно, то будьте добры, с объяснениями, ибо самостоятельно разобраться не особо выходит.
-
Комментариев (0)
-
- 0
-
на фото …………………
-
Комментариев (0)
-
- 0
-
1) Используем формулу a*b=НОК*НОД=14400
2) НОД=20, а это значит что каждое из чисел делиться на 20. Потому можно расписать а=20c , b=20d. C и d натуральные и общих делителей больше единици не имеют(в противном случае НОД был бы больше 20).
3) a*b=20c*20d=14400
c*d=36
Произведение двух чисел не имеющих общих делителей больше единици равно 36 только в двух случаях: c=1, d=36; c=4, d=9;( можно ещё местами c и d поменять, но оно просто продублирует эти два решения, но в другом порядке).
4) Отсюда получим: a=20c=20, b=20d=720-первая пара корней.
a=20c=80, b=20d=180.
5) Ответ: Одно из чисел равно 20, второе 720, или одно из чисел равно 80, второе 180.
-
Комментариев (0)
Начнем с того, что если это числа a и b, то
a*b = НОД*НОК
Кроме того, a = НОД*a1, и b = НОД*b1.
Так что задача — найти такие a1 и b1, у которых НОД=1 (взаимно простые).
a1 = 1 и b1 = НОК/НОД подходят, как одно из решений, так что a = НОД, b = НОК является решением. Прочие можно искать разложением на простые сомножители и перебирать все возможные вариант (а их может оказаться много :)).
Очевидно, что решение существует не для всех с потолка взятых НОД и НОК — как минимум, НОК должно делиться на НОД.
Могут быть и другие решения. Вам нужно найти все решения или любое решение?
Как я понимаю из условия, хватит и одного. Тогда
int GCD, LCM;
cin >> GCD >> LCM;
if (LCM % GCD != 0) cout << -1;
else cout << GCD << " " << LCM/GCD;