Форум программистов, компьютерный форум, киберфорум
Наши страницы
Pascal (Паскаль)
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.60/5: Рейтинг темы: голосов - 5, средняя оценка - 4.60
yutochka123
0 / 0 / 0
Регистрация: 14.11.2014
Сообщений: 55
1

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

30.09.2015, 20:49. Просмотров 931. Ответов 7
Метки нет (Все метки)

Даны натуральные взаимно простые числа n, p. Найдите m такое, что, во-первых, m<p, во-вторых, произведение чисел m и n при делении на p даёт остаток 1.
Помогите пожалуйста!!!
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
30.09.2015, 20:49
Ответы с готовыми решениями:

Алгоритм Евклида
Найти НОД двух положительных чисел с помощью алгоритма евклида

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

Расширенный алгоритм Евклида
Не могу найти решение на Паскале задачи на расширенный алгоритм Евклида: Для...

Функции и Алгоритм Евклида
Помогите пожалуйста! Даны натуральные числа а и b, обозначающие соответственно...

Сокращение дроби (алгоритм Евклида)
Написать программу сокращения дроби p/q, где p и q натуральные числа (Алгоритм...

7
ZX Spectrum-128
Модератор
Эксперт Pascal/Delphi
3876 / 2861 / 3636
Регистрация: 05.06.2014
Сообщений: 14,057
30.09.2015, 20:56 2
yutochka123, внизу страницы "Похожие темы".
0
yutochka123
0 / 0 / 0
Регистрация: 14.11.2014
Сообщений: 55
30.09.2015, 21:05  [ТС] 3
Именно такой нет...
0
ФедосеевПавел
Модератор
3654 / 2027 / 837
Регистрация: 01.02.2015
Сообщений: 6,744
30.09.2015, 21:16 4
Мне кажется, что задача сводится к Диофантовому уравнению
m*n+x*p=1
m, n - из условия,
m, x - найдётся по решению, вернее, там множество решений, нужно будет ограничить m<p.
0
Puporev
Модератор
54584 / 42090 / 29061
Регистрация: 18.05.2008
Сообщений: 99,279
30.09.2015, 21:57 5
Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
function Evclid(x,y:integer):integer;
begin
repeat
if abs(x)>abs(y) then x:=x mod y
else y:=y mod x;
until (x=0) or (y=0);
Evclid:=abs(x+y);
end;
var n,p,m,i:integer;
begin
repeat
writeln('Введите 2 натуральны, взаимно простых числа');
readln(n,p);
until  Evclid(n,p)=1;
writeln('n=',n);
writeln('p=',p);
i:=1;
m:=0;
while (i<p)and(m=0) do
if i*n mod p=1 then m:=i
else inc(i);
if m=0 then write('Искомого числа нет')
else write('m=',m,' ',n,'*',m,'=',n*m,' mod ',p,'=1');
end.
Добавлено через 3 минуты
Цитата Сообщение от ФедосеевПавел Посмотреть сообщение
Мне кажется, что задача сводится к Диофантовому уравнению
Прочитал это и вспомнил про расширенный алгоритм Эвклида, наверное на него задача, как писал такую на форуме.

Добавлено через 4 минуты
Хотя там условие другое...
0
ФедосеевПавел
Модератор
3654 / 2027 / 837
Регистрация: 01.02.2015
Сообщений: 6,744
01.10.2015, 21:11 6
И я думаю, что расширенный алгоритм Эвклида. За счёт двух условий НОД(n,p)=1 и (m*n) mod p = 1 формулы для решения линейного Диофантового уравнения слегка упростятся. А там или по формулам умножения/деления или перебором кратных чисел.

Добавлено через 21 час 46 минут
Решение задачи ТС из переделанной программы для решения диофантовых уравнений. Я не стал переименовывать переменные - оставлю это ТС. Смысл проги вот в чём:
1. Имеется уравнение вида
a*x+b*y=c
которое в переменных условия задачи выглядит
n*m+p*y=1
Т.е. имеем соответствие
a -> n
x -> m
b -> p
y -> y
Можно по всему тексту заменить названия переменных, но для автоматического переименования я выбрал слишком короткие названия, а вручную - лень.
2. Далее математика такая
g:=НОД(a, b) = 1 (по условию задачи)
По формуле
X0:=Xg*(c div g) = Xg*(1 div 1) = Xg
Y0:=Yg*(c div g) = Yg*(1 div 1) = Yg
Решение уравнения с заданными условиями
x:=X0 + b*k
y:=Y0 - a*k
Как мы помним, переменная x соответствует искомой m, которая в свою очередь меньше p ( -> b). Получим
m:=X0+b*k < p
m:=X0+b*k < b
k < (b-X0) div b
Мне сейчас трудно сообразить, возможна ли ситуация, когда (b-X0) нацело делится на b, что приведёт к m=p. Но предположим, что нет.
Тогда
k:=(b-X0) div b
И
m:=X0+b*k
Всё.
Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
{
Решение диофантового a*x+b*y=c уравнения в общем виде
 
Ограничение:
Коэффициенты a и b - только неотрицательные. Для отрицательных
нужно сделать ещё некоторые телодвижения, описанные в e-maxx.
}
program LinearDiophantineEquation;
 
  {Extended Euclidean algorithm}
  {
   на входе:
   a, b
   на выходе:
   НОД(a, b) = GCD(a, b)
   x, y - числа, такие, что a*x+b*y=GCD(a, b)
  }
  function ExtendedEuclideanAlgorithm(a, b: integer; var x, y: integer): integer;
  var
    x1, y1, d: integer;
  begin
    if (a = 0) then
    begin
      x := 0;
      y := 1;
      ExtendedEuclideanAlgorithm := b;
      Exit;
    end;
    d := ExtendedEuclideanAlgorithm(b mod a, a, x1, y1);
    x := y1 - (b div a) * x1;
    y := x1;
    ExtendedEuclideanAlgorithm := d;
  end;
 
var
  a, b, c: integer;
  Xg, Yg, g: integer;
  X0, Y0: integer;
  k: integer;
begin
  a := 10;
  b := 23;
  c := 1;
  {рассмотрим некоторые вырожденные случаи, доступные на данном этапе}
  {
   1. a=0, b=0, c=0 - бесконечное множество решений с произвольными x и y
   2. a=0, b=0, c<>0 - нет ни одного решения
   }
  if (a = 0) and (b = 0) then
  begin
    if (c = 0) then
      writeln('Бесконечное множество решений с любыми значениями x и y.')
    else
      writeln('Нет ни одного решения.');
    Exit;
  end;
  {нахождение НОД(a,b) и дополнительных переменных}
  g := ExtendedEuclideanAlgorithm(a, b, Xg, Yg);
  {на основе новых данных рассмотрим ещё один вырожденный случай
  3. c не делится на GCD(a, b) - нет ни одного решения
  }
  if (c mod g) <> 0 then
  begin
    writeln('Нет ни одного решения.');
    Exit;
  end;
  {нахождение одного решения}
  X0 := Xg * (c div g);
  Y0 := Yg * (c div g);
  {нахождение решения в общем виде}
  (*
  writeln('Решение диофантова уравнения ', a, 'x+', b, 'y=', c, ' в общем виде:');
  writeln('x=', X0, '+', (b div g), 'k');
  writeln('y=', Y0, '-', (a div g), 'k');
  *)
  {теперь подгонка к решению задачи на основе диофантового уравнения}
  k := (b - X0) div b;
  writeln('m=', X0 + b * k, '<', b);
end.
Добавлено через 6 минут
Предвидя вопросы о пояснении - приведу ссылки на мои источники вдохновения: e-maxx и Wikipedia.

Добавлено через 54 минуты
------------------------------------------------------------------------------------
Если посмотреть на результат, возвращаемый расширенным алгоритмом Эвклида, то с учётом взаимной простоты чисел n и p, то получим, что Ng*n+Pg*p=1, что является условием задачи. И принимая во внимание решения для диофантовых уравнений, получим
Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
program task;
 
  {Extended Euclidean algorithm}
  {
   на входе:
   a, b
   на выходе:
   НОД(a, b) = GCD(a, b)
   x, y - числа, такие, что a*x+b*y=GCD(a, b)
  }
  function ExtendedEuclideanAlgorithm(a, b: integer; var x, y: integer): integer;
  var
    x1, y1, d: integer;
  begin
    if (a = 0) then
    begin
      x := 0;
      y := 1;
      ExtendedEuclideanAlgorithm := b;
      Exit;
    end;
    d := ExtendedEuclideanAlgorithm(b mod a, a, x1, y1);
    x := y1 - (b div a) * x1;
    y := x1;
    ExtendedEuclideanAlgorithm := d;
  end;
 
var
  Ng, Pg, g: integer;
  k: integer;
  m, n, p: integer;
begin
  n := 103;
  p := 23;
  {нахождение НОД(n,p) и дополнительных переменных}
  g := ExtendedEuclideanAlgorithm(n, p, Ng, Pg);
  {теперь подгонка к решению задачи на основе диофантового уравнения}
  k := (p - Ng) div p;
  if Ng + p * k >= p then
    Dec(k);
  m := Ng + p * k;
  writeln('m=', m, '<', p);
  writeln('m*n=', m * n, ' mod ', p, ' = ', (m * n) mod p);
end.
0
Puporev
Модератор
54584 / 42090 / 29061
Регистрация: 18.05.2008
Сообщений: 99,279
01.10.2015, 21:13 7
А мне кажется и мой код решает задачу как она описана.
0
ФедосеевПавел
Модератор
3654 / 2027 / 837
Регистрация: 01.02.2015
Сообщений: 6,744
01.10.2015, 21:25 8
Да, согласен на все 100%. Просто хотелось решить другим способом. Это даже не для ТС, а чтобы самому вспомнить математику. Даже видно изменение кода по мере чтения .
0
01.10.2015, 21:25
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
01.10.2015, 21:25

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

Описать рекурсивную функцию NOD(A,B), находящую наибольший общий делитель двух чисел, используя алгоритм Евклида
Описать рекурсивную функцию NOD(A,B) целого типа, находящую наибольший общий...

Даны натуральные числа A и B. Найти их НОК, определив функцию для расчета НОД двух натуральных чисел, используя алгоритм Евклида
Даны натуральные числа A и B. Найти их наименьшее общее кратное, определив...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
8
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru