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

@solomid · Регистрация: 22.09.2011

Студворк — интернет-сервис помощи студентам

доброго времени суток

Даны целые положительные числа a и b. Необходимо найти целые (не обязательно положительные) числа x и y, такие, что
ax+by = НОД(a,b).
Например: a=93, b=53; НОД(93,53)=1 ;93*4 + 53*(-7) = 1
НОД находит без проблем, а вот как реализовать подбор x и y незнаю, подскажите пожалста

C++
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
#include "stdafx.h"
#include <iostream>
#include <stdio.h>
using namespace std;
 
int NOD(int a, int b)
{
    int c;
    while(b)
    {
        c = a%b;
        a=b;
        b=c;
    }
    return a;
}
int DIF(int x,int y)
{
//здесь что-то классное:)
}
int main(void)
{
    int a,b;
    cin >> a;
    cin >> b;
    cout << NOD(a,b) << DIF(x,y) << endl;
    return 0;
}

@Yurii_74 · 12.10.2011, 16:47

Можно в лоб попробовать. x = 1, y = -1. sum = x*A + y*B. Затем, исходя из получившейся суммы, увеличивать x или уменьшать y, Повторять до получения требуемого результата (+НОД(A, B) или -НОД(A, B)).

@aeshes · 12.10.2011, 16:57

вам нужен расширенный алгоритм Евклида

@Yurii_74 · 12.10.2011, 17:04

312	429	39
1	-1	-117	-3
2	-1	195	5
2	-2	-234	-6
3	-2	78	2
3	-3	-351	-9
4	-3	-39	-1
5	-3	273	7
5	-4	-156	-4
6	-4	156	4
6	-5	-273	-7
7	-5	39	1

Это так, небольшой пример-подсказка.

Новые блоги и статьи Все статьи Все блоги /
Модульный подход на примере F# DevAlt 06.03.2026 В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .	Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование 8Observer8 05.03.2026 Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .	SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D 8Observer8 04.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .	SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий 8Observer8 02.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip Сканируйте QR-код на мобильном и вы увидите, что появится джойстик для управления главным героем. . . .
Реалии Hrethgir 01.03.2026 Нет, я не закончил до сих пор симулятор. Эта задача сложнее. Не получилось уйти в плавсостав, но оно и к лучшему, возможно. Точнее получалось - но сварщиком в палубную команду, а это значит, в моём. . .	Ритм жизни kumehtar 27.02.2026 Иногда приходится жить в ритме, где дел становится всё больше, а вовлечения в происходящее — всё меньше. Плотный график не даёт вниманию закрепиться ни на одном событии. Утро начинается с быстрых,. . .	SDL3 для Web (WebAssembly): Сборка библиотек: SDL3, Box2D, FreeType, SDL3_ttf, SDL3_mixer и SDL3_image из исходников с помощью CMake и Emscripten 8Observer8 27.02.2026 Недавно вышла версия 3. 4. 2 библиотеки SDL3. На странице официальной релиза доступны исходники, готовые DLL (для x86, x64, arm64), а также библиотеки для разработки под Android, MinGW и Visual Studio. . . .	SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .

@Yurii_74 paladin 286 / 187 / 7 Регистрация: 25.02.2009 Сообщений: 589
	12.10.2011, 16:47
	Можно в лоб попробовать. x = 1, y = -1. sum = xA + yB. Затем, исходя из получившейся суммы, увеличивать x или уменьшать y, Повторять до получения требуемого результата (+НОД(A, B) или -НОД(A, B)). 0

@aeshes 448 / 211 / 21 Регистрация: 07.10.2011 Сообщений: 462
	12.10.2011, 16:57
	Сообщение было отмечено как решение Решение вам нужен расширенный алгоритм Евклида 3

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

Решение