Решение уравнения ax b mod n (2 видео) | Про уравнения

Решение уравнения

Содержание

Главная > Решение
http://acm.uva.es/problemset : 10104 (Задача Евклида), 10407 (Простое деление), 10548 (Найти правильный размен), 10673 (Игра с округлением вниз и вверх), 10717 (Монетный завод).
Упражнение 1.2. [Вальядолид, 10717]. Монетный завод. Если a , b , c , d – толщины четырех типов монет, то минимально возможная высота стола, который можно сделать, равна h = НОК( a , b , c , d ). Обозначим через low максимально возможную высоту стола, не большую желаемой величины Height . Тогда low должно делиться на h и быть максимально возможным значением, не большим Height . Отсюда
Пример. Рассмотрим набор монет из первого теста, желаемая высота стола равна 1000. Имея 4 монеты с толщинами 50, 100, 200, 400 можно конструировать столы, высоты которых кратны НОК(50, 100, 200, 400) = 400. Искомые высоты столов, которые можно сделать, соответственно равны 800 и 1200.
Пример. Для первого теста ( x = 5, k = 2) имеет место соотношение:
5 = 1 * + 1 * = 1*2 + 1*3.
Solve Linear Congruences Ax = B (mod N) for values of x in range [0, N-1]
Решение уравнения ax b mod n
Псевдокод.
Исходник на Си.
🎥 Видео

Главная > Решение

Информация о документе
Дата добавления:
Размер:
Доступные форматы для скачивания:

1. Наибольший общий делитель. Наименьшее общее кратное. Методы вычисления, свойства.

2. Расширенный алгоритм Евклида. Описание алгоритма. Примеры.

3. Линейные сравнения. Алгоритм решения линейных сравнений вида ax = b (mod n ).

4. Диофантовы уравнения. Решение уравнения ax + by = c в целых неотрицательных числах. Теорема о существовании решения.

5. Обработка строк. Библиотека . Длина строки. Конкатенация и копирование строк. Ввод-вывод строк при помощи функций gets и puts.

Видео:Теория чисел. 6. Методы решения сравнений 1 й степениСкачать

http://acm.uva.es/problemset : 10104 (Задача Евклида), 10407 (Простое деление), 10548 (Найти правильный размен), 10673 (Игра с округлением вниз и вверх), 10717 (Монетный завод).

1. НАИБОЛЬШИЙ ОБЩИЙ ДЕЛИТЕЛЬ. НАИМЕНЬШЕЕ ОБЩЕЕ КРАТНОЕ

Определение 1.1. Наибольшим общим делителем (далее НОД) двух целых чисел a и b , одновременно не равных нулю, называется такое наибольшее целое число d , на которое a и b делятся без остатка. Этот факт обозначается так: d = НОД( a , b ). Если оба числа равны нулю, то положим НОД(0, 0) = 0.

Исходя из определения, имеют место следующие равенства:

НОД( a , b ) = НОД( b , a ),

НОД( a , b ) = НОД(- a , b )

Определение 1.2. Наименьшим общим кратным (далее НОК) двух целых чисел a и b называется наименьшее общее положительное целое число, кратное как a так и b .

Основная теорема арифметики утверждает, что любое натуральное число можно представить в виде произведения простых чисел:

n = =

Из канонического разложения следует, что

НОД( a , b ) =

НОК( a , b ) =

Пример 1.1. Рассмотрим числа a = 24, b = 18. Разложим их на простые множители: 24 = 2 3 * 3, 18 = 2 * 3 2 . Следовательно

НОД(24, 18) = 2 min(3,1) * 3 min(1,2) = 2 1 * 3 1 = 6,

НОК(24, 18) = 2 max(3,1) * 3 max(1,2) = 2 3 * 3 2 = 8 * 9 = 72

Если НОД( a , b ) = d , то a и b делятся на d . Следовательно их разница a – b также делится на d . Имеет место следующее рекурсивное соотношение для вычисления НОД, известное как алгоритм Евклида :

НОД( a , b ) =

Пример 1.2. Пусть a = 32, b = 12. Тогда

НОД(32, 12) = НОД(32 – 12, 12) = НОД(20, 12) = НОД(20 – 12, 12) = НОД(8, 12) =

НОД(8, 12 – 8) = НОД(8, 4) = НОД(8 – 4, 4) = НОД(4, 4) = НОД(4 – 4, 4) = НОД(0, 4) = 4

Приведенный метод вычисления не является оптимальным. Например, для нахождения НОД(100, 2) следует выполнить 50 операций вычитания. Для ускорения вычисления НОД операцию вычитания следует заменить операцией взятия остатка от деления:

НОД( a , b ) =

Пример 1.3. Пусть a = 78, b = 14. Тогда

НОД(78, 14) = НОД(78 mod 14, 14) = НОД(8, 14) = НОД(8, 14 mod 8) = НОД(8, 6) =

НОД(8 mod 6, 6) = НОД(2, 6) = НОД(2, 6 mod 2) = НОД(2, 0) = 2

Упростим приведенную выше рекуррентность:

НОД( a , b ) =

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

Используя тернарный оператор, функцию gcd ( Greater Common Divisor ) вычисления НОД можно записать в виде:

int gcd(int a, int b)

return (!b) ? a : gcd(b,a % b);

Пример 1.4. Пусть a = 14, b = 78. Тогда

НОД(14, 78) = НОД(78, 14) = НОД(14, 8) = НОД(8, 6) = НОД(6, 2) = НОД(2, 0) = 2

Бинарный алгоритм вычисления НОД имеет вид:

НОД(2* a , 2* b ) = 2*НОД( a , b ), если a и b четно

НОД(2* a , b ) = НОД( a , b ), если a четно, b нечетно

НОД( a , 2* b ) = НОД( a , b ), если a нечетно, b четно

НОД( a , b ) = НОД( a – b , b ), если a нечетно, b нечетно, a > b

НОД( a , b ) = НОД( a , b – a ), если a нечетно, b нечетно, a  b

Теорема 1.1. Между НОД и НОК двух чисел имеет место соотношение:

a * b = НОД( a , b ) * НОК( a , b )

Функция lcm ( Lowest Common Multiple ) вычисления НОК имеет вид:

int lcm(int a, int b)

return a * b / gcd(a,b);

Заметим, что при вычислении выражения a * b / gcd( a , b ) может возникнуть переполнение, а при a / gcd( a , b ) * b нет. Здесь подразумевается, что значения a , b и lcm( a , b ) лежат в границах типа int.

Упражнение 1.1. [Вальядолид, 10407]. Простое деление. При делении числа n на d получается частное q и остаток r . При этом q – максимально возможное целое, для которого qd  n , а r = n – qd . Для любого множества целых чисел всегда существует такое d , что числа a i mod d равны.

Вход. Каждая строка является отдельным тестом и содержит последовательность чисел a 1 , …, a k , заканчивающуюся нулем. Последний ноль не принадлежит самой последовательности. Последовательность содержит не менее 2 и не более 1000 чисел. Не все числа в последовательности равны между собой. Признаком конца входных данных является строка с одним нулем.

Выход. Для каждой входной последовательности a 1 , …, a k найти максимальное d , для которого при делении a i на d будут получаться равные остатки.

701 1059 1417 2312 0

14 23 17 32 122 0

14 -22 17 -31 -124 0

Упражнение 1.2. [Вальядолид, 10717]. Монетный завод. Канадский королевский завод производит столы, ножки которых составляют из куп монет. Каждый стол имеет четыре ножки, а каждая ножка должна состоять из разных типов монет. Например, одна ножка может состоять из четвертушек, другая – из десяток, третья – из одноцентовых, а четвертая – из двухцентовых монет. Имеется конечное количество типов монет. Количество монет каждого типа неограниченно. Известна толщина каждого типа монет. Необходимо определить максимально возможную высоту стола, не большую заданной величины и минимально возможную высоту стола, не меньшую заданной величины.

Вход. Состоит из нескольких тестов. Первая строка каждого теста содержит количество доступных номиналов монет n (4  n  50) и количество столов T (1  T  10), которое следует сделать. Следующие n строк характеризуют толщину монет. Далее идут T строк, описывающих желаемые высоты столов, которые следует сконструировать. Последний тест содержит n = T = 0 и не обрабатывается.

Выход. Для каждого теста вывести максимально возможную высоту стола, не большую желаемой и минимально возможную высоту стола, не меньшую желаемой.

2. РАСШИРЕННЫЙ АЛГОРИТМ ЕВКЛИДА

Алгоритм Евклида можно расширить для нахождения по заданным a и b таких целых x и y , что ax + by = d , где d – наибольший общий делитель a и b .

Лемма. Пусть для положительных целых чисел a и b ( a > b ) известны d = НОД( a , b ) = НОД( b , a mod b ), а также числа x ’ и y ’, для которых

d = x ’ * b + y ’ * ( a mod b )

Тогда значения x и y , являющиеся решениями уравнения ax + by = d , находятся из соотношений

x = y ’, y = x ’ – y ’ *

Через здесь обозначена целая часть числа x .

Доказательство. Поскольку a mod b = a – * b , то

d = x ’ * b + y ’ * ( a – * b ) = y ’ * a + ( x ’ – y ’ * ) * b = x * a + y * b ,

где обозначено x = y ’, y = x ’ – y ’ * .

Функция gcdext(int a , int b , int * d , int * x , int * y ), приведенная ниже, по входным числам a и b находит d = НОД( a , b ) и такие x , y что d = a * x + b * y . Для поиска неизвестных x и y необходимо рекурсивно запустить функцию gcdext( b , a mod b , d , x , y ) и пересчитать значения x и y по выше приведенной формуле. Рекурсия заканчивается, когда b = 0. При b = 0 НОД( a , 0) = a и a = a * 1 + 0 * 0, поэтому полагаем x = 1, y = 0.

void gcdext(int a,int b, int *d, int *x, int *y)

Для ручного выполнения расширенного алгоритма Евклида удобно воспользоваться таблицей с четырьмя столбцами (как показано ниже в примере), соответствующих значениям a , b , x , y . Процесс вычисления разделим на три этапа:

а) Сначала вычислим НОД( a , b ), используя первые два столбца таблицы и соотношение (1). В последней строке в колонке а будет находиться значение d = НОД( a , b ).

б) Занесем значения 1 и 0 соответственно в колонки x и y последней строки.

в) Будем заполнять последовательно строки для колонок x и y снизу вверх. Значения x и y в последнюю строку уже занесены на этапе б). Считая, что в текущей заполненной строке уже находятся значения ( x ’, y ’), мы при помощи формул (2) будем пересчитывать и записывать значения ( x , y ) в соответствующие ячейки выше стоящей строки.

Пример. Расширенный алгоритм Евклида. Найдем решение уравнения 5 x + 3 y = 1. Вычисление НОД(5, 3) и нахождение соответствующих x , y произведем в таблице:

Порядок и направление вычислений указаны стрелками и буквами.

Из таблицы находим, что НОД(5, 3) = 5 * (-1) + 3 * 2 = 1, то есть x = -1, y = 2.

Рассмотрим, например, как получены значения ( x , y ) для первой строки. Со второй строки берем значения ( x ’, y ’) = (1, -1). По формулам (2) получим:

y = x ’ – y ’ * = 1 – (-1) * = 1 + 1 = 2

Упражнение 2.1. [Вальядолид, 10104]. Задача Евклида. Со времен Евклида известно, что для любых положительных a и b существуют такие целые x и y , что ax + by = d , где d – наибольший общий делитель a и b . По заданным a и b найти x , y , d .

Вход. Каждая строка содержит два числа a и b , разделенных пробелом ( a , b  10 9 ).

Выход. Для каждого теста вывести три числа x , y , d , разделенных пробелом. Если существует несколько пар x и y , то вывести ту пару, для которой x  y и выражение | x | + | y | минимально.

Упражнение 2.2. [Вальядолид, 10673] Игра с округлением вниз и вверх.

Теорема. Для двух целых чисел x и k всегда существуют такие целые p и q , что

x = p + q

По заданным x и k необходимо найти хотя бы одну такую пару p и q .

Вход. Первая строка содержит количество тестов t (1  t  1000). Каждая следующая строка содержит два положительных целых числа x и k ( x , k 8 ).

Выход. Для каждого теста вывести в отдельной строке два числа: p и q . Если таких пар существует несколько, то вывести одну из них. Значения p и q помещаются в 64-битовый целый тип.

3. ЛИНЕЙНЫЕ СРАВНЕНИЯ

Линейным сравнением называется уравнение вида ax = b (mod n ). Оно имеет решение тогда и только тогда, когда b делится на d = НОД( a , n ). Если d > 1, то уравнение можно упростить, заменив его на a ’ x = b ’ (mod n ’), где a ’ = a / d , b ’ = b / d , n ’ = n / d . После такого преобразования числа a ’ и n ’ являются взаимно простыми.

Алгоритм решения уравнения a ’ x = b ’ (mod n ’) со взаимно простыми a ’ и n ’ состоит из двух частей:

1. Решаем уравнение a ’ x = 1 (mod n ’). Для этого при помощи расширенного алгоритма Евклида ищем решение ( x 0 , y 0 ) уравнения a ’ x + n ’ y = 1. Взяв по модулю n ’ последнее равенство, получим a ’ x 0 = 1 (mod n ’).

2. Умножим на b ’ равенство a ’ x 0 = 1 (mod n ’). Получим a ’( b ’ x 0 ) = b ’ (mod n ’), откуда решением исходного уравнения a ’ x = b ’ (mod n ’) будет x = b ’ x 0 (mod n ’).

Лемма. Если НОД( k , m ) = 1, то равенство ak = bk (mod m ) эквивалентно a = b (mod m ).

Доказательство. Из ak = bk (mod m ) следует, что ( a – b ) * k делится на m . Но поскольку k и m взаимно просты, то a – b делится на m , то есть a = b (mod m ).

Пример. Решить уравнение 18 x = 6 (mod 8).

Значение d = НОД(18, 8) = 2 является делителем 6, поэтому решение существует. После упрощения получим уравнение 9 x = 3 (mod 4). Что согласно лемме эквивалентно 3 x = 1 (mod 4). Решая уравнение 3 x + 4 y = 1 с помощью расширенного алгоритма Евклида, получим x = -1, y = 1. Откуда x = -1 (mod 4) = 3. То есть x = 3 будет как решением уравнения 3 x = 1 (mod 4), так и 18 x = 6 (mod 8).

4. ДИОФАНТОВЫ УРАВНЕНИЯ

Диофантовыми уравнениями называются уравнения вида

P ( x 1 , x 2 , . x n ) = 0,

где P ( x 1 , . x n ) – многочлен с целыми коэффициентами.

В этой главе рассмотрим алгоритм нахождения решения линейного диофантового уравнения с двумя неизвестными: a * x + b * y = c .

Теорема 3.1. Уравнение a * x + b * y = c имеет решения в целых числах тогда и только тогда, когда c делится на НОД( a , b ).

Теорема 3.2. Если пара ( x 0 , y 0 ) является решением уравнения ax + by = c , то все множество его решений ( x , y ) описывается формулой:

где k  Z. При этом a ( x + kb ) + b ( y – ka ) = c .

Для нахождения хотя бы одного решения ( x 0 , y 0 ) уравнения ax + by = c следует найти решение ( x ’, y ’) уравнения ax + by = d ( d – наибольший общий делитель чисел a и b ) при помощи расширенного алгоритма Евклида, после чего умножить полученное решение на k = c / d . То есть

Пример 3.1. Найти множество решений уравнения 5* x + 3* y = 7.

1. Уравнение имеет решения, так как d = НОД(5, 3) = 1, 7 делится на 1.

2. Находим решение уравнения 5* x ’ + 3* y ’ = 1 при помощи расширенного алгоритма Евклида (пример 1.2.1): ( x ’, y ’) = (-1, 2).

3. Находим решение ( x 0 , y 0 ) исходного диофантового уравнения:

x 0 = -1 * 7 / 1 = -7,

y 0 = 2 * 7 / 1 = 14

Согласно теореме 1.3.2. множество решений диофантового уравнения имеет вид:

( x , y ) = (-7 + 3* k , 14 – 5* k )

Упражнение 3.1. [Вальядолид, 10548]. Найти правильный размен. В древние времена люди вместо денег обменивались товарами. В наличии имеются два типа товаров: A и B. Покупатель желает приобрести товар на сумму c > 0. Стоимости товаров A и B соответственно равны a и b . Если одно из значений a или b отрицательно, то продавец может этим товаром давать сдачу. Одновременно отрицательными a и b быть не могут. Сколькими способами покупатель может приобрести товар на сумму c , если это возможно?

Вход. Первая строка содержит количество тестов n (0 n a , b и c (0 a |, | b |, | c | 31 ).

Выход. Для каждого теста вывести количество комбинаций, которыми покупатель может приобрести товар ровно на сумму c . Если приобрести товар невозможно, то вывести сообщение “Impossible”. Если число комбинаций бесконечно, то вывести “Infinitely many solutions”.

Infinitely many solutions

5. ОБРАБОТКА СТРОК

В этом разделе мы не будем касаться класса string, а рассмотрим, как обрабатывались строки на языке Си до появления стандартной библиотеки шаблонов.

Строки представляются в памяти компьютера как массив элементов char и объявляются следующим образом:

Первый символ строки доступен как s[0] (нулевой элемент массива), второй символ – как s[1] и так далее. В конце строки всегда стоит символ ‘’ (нуль-символ). То есть строки в Си завершаются нулем. Такой подход позволяет снять ограничения с длины строк. Строка может быть такой длины, какой позволяет память для ее хранения. Символ ‘’ не видим в строковом выражении, но он добавляется как последний элемент при запоминании строки. Например, в объявленную выше строку s можно записать не более 9 букв, а строка “ABC” содержит 4 символа, а не три.

Пример 4.1. Рассмотрим объявление строк и их вывод.

// Объявим две строки s и t. Строку t проинициализируем данными.

char s[10],t[10] = «This»;

//Для вывода строк при помощи функции printf пользуются форматом “%s”:

//Вывести строку можно и при помощи цикла посимвольно:

for(i = 0; t[i]; i++) printf(«%c»,t[i]); printf(«n»);

В случае посимвольного вывода строки цикл продолжается до тех пор, пока очередной выводимый символ не будет иметь ASCII код, равный 0. Однако таким выводом строк, как правило, не пользуются.

Для работы со строками существует набор функций, объявленный в библиотеке . Рассмотрим некоторые из них.

size_t strlen(const char *string)

char *strcpy(char *s1, const char *s2)

Копирует строку s2, включая символ ‘’, в область памяти, начинающейся с адреса s1. Возвращает s1.

char *strcat(char *s1, const char *s2)

Конкатенация строк s1 и s2. Строка s2 дописывается в конец s1.

char *strcpy (char *destination, const char *source);

Копирование строки source в destination.

Пример 4.2. Объявим строку s и найдем ее длину.

printf(«Length of %s is %dn»,s,strlen(s));

Пример 4.3. Создадим строку t , состоящую из 10 копий “abc”.

char s[] = «abc», t[31];

for(i = 0; i Пример 4.4. Присваивать строки, представляющие собой массивы символов, при помощи оператора “=” нельзя. Необходимо копировать содержимое из одной строки в другую при помощи функции strcpy.

char s[10] = «Hello», t[10];

Пример 4. 5 . При чтении строки с помощью формата %s считывается последовательность символов, не содержащая пробелов. Например, если на вход следующей программы подать текст ”This is a cat”, то каждый раз функция scanf будет считывать только одно слово. Цикл повторяется 4 раза (входной текст содержит 4 слова). При этом выводятся слова слитно, так как печать между ними пробела не предусмотрена программой.

for(i = 0; i

char *gets(char *s)

чтение строки в символьный массив s

int puts(const char *s)

вывод строки на консоль

Функция gets читает всю строку в массив s независимо от символов, которые она содержит. То есть если подать на вход текст ”This is a cat”, то функция gets(s) запишет его полностью в массив s, при этом занеся 0 в конец строки.

Пример 4. 6 . Прочитать текст и вывести его на консоль. Длина каждой строки не более 100.

УКАЗАНИЯ К РЕШЕНИЮ УПРАЖНЕНИЙ

Упражнение 1.1. [Вальядолид, 10407]. Простое деление. Из условия задачи следует, что

a 1 = d * r 1 + rest

a 2 = d * r 2 + rest

a k = d * r k + rest

Поскольку d максимально , то НОД( r 1 , r 2 , …, r n ) = 1. Далее имеем:

a 2 – a 1 = d * ( r 2 – r 1 )

a 3 – a 2 = d * ( r 3 – r 2 )

a k – a k -1 = d * ( r k – r k -1 )

Откуда d = НОД(| a 2 – a 1 |, | a 3 – a 2 |, …, | a k – a k -1 |).

Реализация. Основной цикл программы состоит в чтении последовательности чисел и последовательном вычислении значения НОД(| a 2 – a 1 |, | a 3 – a 2 |, …, | a k – a k -1 |).

int gcd(int a, int b)

return (!b) ? a : gcd(b, a % b);

res = abs(a-b); a = b;

Видео:Как решать уравнения с модулем или Математический торт с кремом (часть 1) | Математика Скачать

Упражнение 1.2. [Вальядолид, 10717]. Монетный завод. Если a , b , c , d – толщины четырех типов монет, то минимально возможная высота стола, который можно сделать, равна h = НОК( a , b , c , d ). Обозначим через low максимально возможную высоту стола, не большую желаемой величины Height . Тогда low должно делиться на h и быть максимально возможным значением, не большим Height . Отсюда

low = * h

Если вычисленное low равно Height (что возможно в случае когда Height делится на h без остатка), то минимально возможная высота стола more , не меньшая Height , также равна Height . Иначе она равна low + h .

Остается перебрать все возможные четверки толщин номиналов монет и вычислить максимум среди всевозможных low и минимум среди всевозможных more .

Видео:Решение линейных сравнений ax≡b(mod m). Часть 1. (a, m)=1Скачать

Пример. Рассмотрим набор монет из первого теста, желаемая высота стола равна 1000. Имея 4 монеты с толщинами 50, 100, 200, 400 можно конструировать столы, высоты которых кратны НОК(50, 100, 200, 400) = 400. Искомые высоты столов, которые можно сделать, соответственно равны 800 и 1200.

Реализация. Входные тесты подобраны так, что при решении задачи следует работать с типом unsigned (32 — битовое целое, положительное). Объявим все переменные типа unsigned.

unsigned gcd(unsigned a,unsigned b)

return !a ? b : gcd(b%a,a);

for(i=0;i Height проводим выше описанный алгоритм. Обозначим через Less максимум среди всевозможных low , а через Greater – минимум среди всевозможных more . Проинициализируем их.

Перебираем все возможные четверки номиналов монет x 1 x 2 x 3 x 4 (номиналы монет хранятся соответственно в coins[ x 1], coins[ x2 ], coins[ x 3], coins[ x 4]).

for(x1=0;x1 x 1], coins[ x2 ], coins[ x 3], coins[ x 4]).

g = coins[x1] * coins[x2] / gcd(coins[x1],coins[x2]);

g = g * coins[x3] / gcd(g,coins[x3]);

g = g * coins[x4] / gcd(g,coins[x4]);

Для каждой четверки номиналов пересчитываем значения Less и Greater .

low = Height / g * g;

if (low > Less) Less = low;

if (low != Height) low += g;

if (low Упражнение 2.1. [Вальядолид, 10104]. Задача Евклида. Описание алгоритма приведено в разделе 2.

Реализация. Для решения задачи достаточно прочитать входные данные, вызвать функцию gcdext и напечатать результат.

void gcdext(int a,int b, int *d, int *x, int *y)

while(scanf(«%d %d»,&a,&b) == 2)

Упражнение 2.2. [Вальядолид, 10673]. Игра с округлением вниз и вверх. Если x нацело делится на k , то = = x / k . Выбрав p = 0, q = k , получим: 0 * ( x / k ) + k * ( x / k ) = x . Пусть x не делится на k . Если n = , то m = = n + 1. Поскольку НОД( n , m ) = НОД( n , n + 1) = 1, то исходя из расширенного алгоритма Евклида, существуют такие целые t и u , что 1 = tn + um . Помножив равенство на x , получим x = xtn + xum , откуда p = xt , q = xu .

Видео:How to calculate a power b modulus n i.e (a ^ b mod n)Скачать

Пример. Для первого теста ( x = 5, k = 2) имеет место соотношение:

Видео:✓ Сравнение по модулю. Арифметика остатков | Ботай со мной #034 | Борис ТрушинСкачать

5 = 1 * + 1 * = 12 + 13.

Реализация. При вычислении используем 64-битовый целый тип long long.

typedef long long i64;

i64 tests, x, k, g, t, u;

void gcdext(i64 a,i64 b, i64 *d, i64 *x, i64 *y)

Если k = 0, то устанавливаем p = 0, q = k .

Иначе вычисляем n = , m = и запускаем на числах n и m расширенный алгоритм Евклида. Он находит такие t и u , что 1 = tn + um . Далее вычисляем p = xt , q = xu и выводим результат.

n = (int)floor(1.0 * x / k);

m = (int)ceil(1.0 * x / k);

p = t * x; q = u * x;

Упражнение 3.1. [Вальядолид, 10548]. Найти правильный размен . Если покупатель приобретет x штук товара A и y штук товара B, заплатив при этом сумму c , то получим уравнение ax + by = c . Уравнение имеет решения тогда и только тогда, когда c делится на НОД( a , b ).

Если одно из значений a или b отрицательно, то уравнение ax + by = c имеет бесконечно много решений. Действительно, если ( x 0 , y 0 ) – решение, то пара ( x 0 + kb , y 0 – ka ) будет также решением для любого целого отрицательного k , для которого y 0 – ka  0 (если b k , для которого x 0 + kb  0 (если a a и b положительны, сокращаем a , b , c на их общий делитель и при помощи расширенного алгоритма Евклида находим x ’, y ’, для которых ax ’ + by ’ = 1. Помножив последнее равенство на c и положив x 0 = cx ’ и y 0 = cy ’, получим пару ( x 0 , y 0 ), являющуюся решением уравнения ax + by = c .

Из теоремы 2 следует, что все решения уравнения имеют вид ( x 0 + kb , y 0 – ka ), где k – целое число. Поскольку в задаче решения должны быть неотрицательными, то имеют место следующие неравенства: x 0 + kb  0, y 0 – ka 0. Откуда имеем следующие ограничения: k  , k . Количество решений уравнения ax + by = c , для которых x 0, y  0, равно – + 1.

Пример . Рассмотрим первый тест, где следует найти количество решений уравнения 2 x + 3 y = 17 в целых неотрицательных числах. Числа 2 и 3 взаимно простые, находим x ’и y ’, для которых 2 x ’ + 3 y ’ = 1. Из расширенного алгоритма Евклида имеем: x ’ = -1, y ’ = 1. Помножив их на 17, получим x 0 = 17 x ’ = -17, y 0 = 17 y ’ = 17. Имея частичное решение ( x 0 , y 0 ) = (-17, 17), можно описать множество всех решений исходного уравнения согласно теореме 2: x = -17 + 3 k , y = 17 – 2 k . Они должны быть неотрицательными, следовательно -17 + 3 k  0, y = 17 – 2 k  0. Или то же самое что 3 k  17, 17  2 k . Откуда k  = 6, k  = 8. Объединяя ограничения на k , получим: 6  k  8. То есть существует 3 варианта размена, которые можно получить, подставив в общее решение значения k = 6, 7, 8. Например, при k = 6 получим решение (1, 5), при k = 7 решение (4, 3), а при k = 8 решением будет пара (7, 1).

Для второго теста имеем уравнение 2 x – 3 y = 5. Одним из его решений будет x 0 = 1, y 0 = -1. Все множество решений описывается формулой: x = 1 – 3 k , y = -1 – 2 k . Для всех отрицательных k значения x и y будут положительными и удовлетворять условию задачи.

Для третьего теста решений не существует, так как для любых натуральных x и y значение 10 x + 36 y всегда четно и не может равняться 7 (7 не делится на НОД(10, 36) = 2).

Реализация. При вычислении используем 64-битовый целый тип long long. Для простоты использования переопределим тип long long на i64.

typedef long long i64;

i64 kmin, kmax, res;

i64 gcd(i64 a, i64 b)

return (!a) ? b : gcd(b % a, a);

void gcdext(i64 a,i64 b, i64 *d, i64 *x, i64 *y)

for(i = 0; i d чисел a и b . Если c не делится на d , то выводим сообщении о невозможности произведения размена.

Если a или b отрицательно, то существует бесконечно много вариантов выполнения размена.

if ((a a , b , c на их общий делитель d . Запускаем процедуру расширенного алгоритма Евклида и находим пару ( x , y ) – решение уравнения ax + by = c .

Ищем нижнюю kmin и верхнюю kmax границы для переменной k , откуда и получаем количество решений уравнения ax + by = c . Поскольку a , b , x , y – целые, то чтобы не потерять точность вычислений, помножим дроби – x / b и y / a на действительное число 1.0.

kmin = (i64)ceil(-1.0 * x / b); kmax = (i64)floor(1.0 * y / a);

res = (i64)kmax — kmin + 1;

Если значение res не равно нулю, то выводим его. Иначе печатаем сообщение о том, что произвести размен невозможно.

if (res) printf(«%lldn»,res); else printf(«Impossiblen»);

Видео:Т.чисел 10. Система сравнений. Два метода решенияСкачать

Solve Linear Congruences Ax = B (mod N) for values of x in range [0, N-1]

Given three positive integers A, B, and N, which represent a linear congruence of the form AX=B (mod N), the task is to print all possible values of X (mod N) i.e in the range [0, N-1] that satisfies this equation. If there is no solution, print -1.

Examples:

Input: A=15, B=9, N=18
Output: 15, 3, 9
Explanation: The values of X satisfying the condition AX=B (mod N) are .
(15*15)%18 = 225%18=9
(3*15)%18 = 45%18=9
(9*15)%18 = 135%18=9

Input: A=9, B=21, N=30
Output: 9, 19, 20

Approach: The idea is based on the following observations:

A solution exists if and only if B is divisible by GCD(A, N) i.e B%GCD(A, N)=0.
The number of solutions for X (mod N) is GCD(A, N).

Proof:

Given, AX=B (mod N)
⇒ there exist a number Y such that AX=B+NY
AX-NY=B — (1)
This is a linear Diophantine equation, and is solvable if and only if GCD(A, N) divides B.
Now, using the Extended Euclidean Algorithm,u and v can be found such that Au+Nv=GCD(A, N)=d(say)
⇒ Au+Nv=d
⇒ Au=d (mod N) — (2)
Assuming B%d=0, so that solution of Equation 1 exists,
Multiplying both sides of Equation 2 by B/d, (possible since B/d is an integer),
Au*(B/d)=d*(B/d) (mod N) or A*(u*B/d)=B (mod N).
Thus, u*B/d is a solution of Equation 1.
Let X0 be u*B/d.
Thus, the d solutions of Equation 1 will be X0, X0+(N/d), X0+2*(N/d), …, X0+(d-1)*(N/d)

Follow the steps below to solve the problem:

Initialize variable d as GCD(A, N) as well as u using the Extended Euclidean Algorithm.
If B is not divisible by d, print -1 as the result.
Else iterate in the range[0, d-1] using the variable i and in each iteration print the value of u*(B/d)+i*(N/d).

Below is the implementation of the above approach:

Видео:Решение линейных сравнений ax≡b(mod m). Часть 2. (a,m)≠1Скачать