Форум программистов, компьютерный форум CyberForum.ru
Наши страницы

C++

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 23, средняя оценка - 4.87
Zavulon
0 / 0 / 0
Регистрация: 08.12.2010
Сообщений: 3
#1

Cравнения первого степеня вида ax=b(mod m) - C++

09.12.2010, 02:28. Просмотров 2923. Ответов 1
Метки нет (Все метки)

Помогите решить сравнения первого степеня вида ax=b(mod m) и написать программу, решаюшую такие уравнения на C++.

Пример: 2х=5(mod 3). Остаток m -> [0], [1], [2].
x1=0 -> 2*0-5/3=-5/3 не принадлежит Z. Следовательно, x1=0 не есть решением.
x2=1 -> 2*1-5/3=-1 принадлежит Z. Следовательно, x2=1 есть решением.
x3=2 -> 2*2-5/3=-1/3 не принадлежит Z. Следовательно, x3=2 не есть решением.

Это примерный алгоритм решения для простых уравнений. Если имеются уравнения вида: 124х=72(mod 152), то вручную перебирать их затруднительно, нужно, чтобы это делала программа. Пожалуйста, обьясните коды доступно.
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
09.12.2010, 02:28
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Cравнения первого степеня вида ax=b(mod m) (C++):

Построить три вида фигуры. На месте вида спереди и вида слева совместить часть вида с частью разреза - AutoCAD

вычислить A:= 4*7 mod 5 div 2/3 - trunc(0.724) B:= Abs (round (5/2)-7 div 15+8 mod 9) - Turbo Pascal
A:= 4*7 mod 5 div 2/3 - trunc(0.724) B:= Abs (round (5/2)-7 div 15+8 mod 9)

1.Докажите, что если a ≡ b (mod n) и c ≡ d (mod n), то: - Алгебра
1.Докажите, что если a ≡ b (mod n) и c ≡ d (mod n), то:

Для праздничного чаепития необходимо купить n пирожных. В магазине продается всего два вида пирожных одного вида, причем пирожных одного вида осталось - Pascal ABC
Для праздничного чаепития необходимо купить n пирожных. В магазине продается всего два вида пирожных одного вида, причем пирожных одного...

Как скопировать данные из одного вида таблицы в другою иного вида - MS Excel
Добрый день уважаемые гуру! Вопрос в следующем: есть необходимость скопировать данные из таблицы в листе "накладная" из ячейки B3 в лист...

Написать функцию которая по линейныму списку вида (1 2 3 4 5) строит сложный список вида(1) (2) (3) (4) (5) - Lisp
Здравствуйте. Помогите написать функцию которая по линейныму списку вида (1 2 3 4 5) строит сложный список вида((1) (2) (3) (4) (5)).

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Zavulon
0 / 0 / 0
Регистрация: 08.12.2010
Сообщений: 3
14.12.2010, 00:34  [ТС] #2
хм, господа, в чем дело?
мне нужно не решение этих производных, а именно программа. Может, не там тему подняла? Если да, то переместите пожалуйста.
Алгоритм решения сравнений первой степени http://www.cyberforum.ru/cgi-bin/latex.cgi?ax\equiv b\left(mod m \right):
Возьмем для примера http://www.cyberforum.ru/cgi-bin/latex.cgi?124x\equiv 72\left(mod 152 \right)
1. Найдем НОД http://www.cyberforum.ru/cgi-bin/latex.cgi?\left(a,m \right)=d с помощью алгоритма Евклида:
а) Если http://www.cyberforum.ru/cgi-bin/latex.cgi?m>a, то:
http://www.cyberforum.ru/cgi-bin/latex.cgi?m=aq_0+r_1;<br />
a=r_1q_1+r_2;<br />
r_1=r_2q_2+r_3;<br />
...<br />
r_n-1=r_nq_n.
б) Если http://www.cyberforum.ru/cgi-bin/latex.cgi?m<a, то:
http://www.cyberforum.ru/cgi-bin/latex.cgi?a=mq_0+r_1;<br />
m=r_1q_1+r_2;<br />
r_1=r_2q_2+r_3;<br />
...<br />
r_n-1=r_nq_n.
Тогда наибольший общий делитель http://www.cyberforum.ru/cgi-bin/latex.cgi?d=r_n.
2. Далее рассматриваются два случая:
а) Если http://www.cyberforum.ru/cgi-bin/latex.cgi?b не кратно http://www.cyberforum.ru/cgi-bin/latex.cgi?d, то у сравнения нет решения.
б) Если http://www.cyberforum.ru/cgi-bin/latex.cgi?b кратно http://www.cyberforum.ru/cgi-bin/latex.cgi?d, то у сравнения есть ровно http://www.cyberforum.ru/cgi-bin/latex.cgi?d решений.
3. Сокращаем уравнение на http://www.cyberforum.ru/cgi-bin/latex.cgi?d: http://www.cyberforum.ru/cgi-bin/latex.cgi?\frac{a}{d}x=\frac{b}{d}\left(mod \frac{m}{d} \right) так, чтобы http://www.cyberforum.ru/cgi-bin/latex.cgi?a и http://www.cyberforum.ru/cgi-bin/latex.cgi?m стали взаимно простыми числами http://www.cyberforum.ru/cgi-bin/latex.cgi?\left(\frac{a}{d}, \frac{m}{d} \right)=1
4. Снова используем алгоритм Евклида для http://www.cyberforum.ru/cgi-bin/latex.cgi?\left(a_1, m_1 \right)=1:
Тоже самое, что и в 1.а)\1.б)
5. Таблица для нахождения числителей подходящих дробей:
a) Если http://www.cyberforum.ru/cgi-bin/latex.cgi?m>a, то:
_____________________________________________
|Q_n:| 0 | q_0 | q_1 | ... | q_n |
|____|___|_____|__________|___|_______________|
|P_n:| 1 | q_0 | q_0q_1+1 | ... | p_n-1q_n+p_n-2 |
|____|___|_____|__________|___|_______________|
б) Если http://www.cyberforum.ru/cgi-bin/latex.cgi?m<a, то:
_______________________________________________________________
|Q_n:| 0 | 0 | q_0 | q_1 | q_2 | ... | q_n |
|____|___|___|_____|__________|__________|_____|________________|
|P_n:| 1 | 0 | 1 | q_1 | q_1q_2+1 | ... | p_n-1q_n+p_n-2 |
|____|___|___|_____|__________|__________|_____|________________|
6. И наконец, http://www.cyberforum.ru/cgi-bin/latex.cgi?x\equiv {\left(-1 \right)}^{n-1}b{P}_{n-1}\left(mod m \right).
Причем значение икса не должно перевышать http://www.cyberforum.ru/cgi-bin/latex.cgi?0<x<m-1.
Если http://www.cyberforum.ru/cgi-bin/latex.cgi?x\neq [0,m-1], то к значению http://www.cyberforum.ru/cgi-bin/latex.cgi?x прибавляем http://www.cyberforum.ru/cgi-bin/latex.cgi?m_1 до тех пор, пока http://www.cyberforum.ru/cgi-bin/latex.cgi?x=[0,m_1] .
Вот собсно, и все
ЗЫ: извиняюсь за ужасную таблицу
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
14.12.2010, 00:34
Привет! Вот еще темы с ответами:

Написать функцию которая по линейныму списку вида (a d r g h .) строит сложный список вида (a (d (r (g (h (.) - Lisp
Написать функцию которая по линейныму списку вида (a d r g h ...) строит сложный список вида (a (d (r (g (h (...)))))).

Написать функцию которая по линейныму списку вида ( . a s w c b) строит сложный список вида (.) a) s) w) c) b) - Lisp
Написать функцию которая по линейныму списку вида ( ... a s w c b) строит сложный список вида ((((((...) a) s) w) c) b).

Преобразовать строку вида 1.0.0.0 в числовой формат вида 1000 - C#
Привет уважаемые! Вопрос следующий: каким образом можно преобразовать строку вида 1.0.0.0 в числовой формат вида 1000 быть может не...

Создать 2 вида меню Fox: произвольного и вертикального вида. На основании данных примеров сделать свои типы меню - FoxPro
Создать 2 вида меню Fox: произвольного и вертикального вида. На основании данных примеров сделать свои типы меню, в меню должны быть...


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

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

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