Интегральное решение уравнения `a + bx = c + dy`

В уравнении a + bx = c + dyвсе переменные являются целыми числами. a, b, c, а также d известны. Как мне найти интегральные решения для x а также y? Если я думаю правильно, будет бесконечное число решений, разделенных наименьшим общим кратным b а также d, но все, что мне нужно, это одно решение, а я могу рассчитать остальное. Вот пример:

a = 2
b = 3
c = 4
d = 5
a + bx: (2, 5,  8, 11, 14)
c + dy: (4, 9, 14, 19, 24)

a + bx intersects c + dy at 14, so:
x = 4
y = 2

Прямо сейчас я перебираю интегральные значения x пока я не найду интегральное значение для y (Псевдокод):

function integral_solution(int a, int b, int c, int d) {
// a + bx == c + dy
// (a + bx - c) / d == y

// Some parameters may have no integral solution,
// for example if b == d and (a - c) % b != 0
// If we don't have a solution before x == d, there is none.

int x = 0;
while (x < d)
{
if ((a + bx - c) % d == 0)
{
return [x, (a + bx - c) / d];
}
x++;
}
return false;
}

Я чувствую, что есть лучший способ сделать это. Есть ли способ найти х и у без петли? Я использую C ++, если это имеет какое-либо значение.

7

Решение

Линейный диофантов уравнения принимают форму ax + by = c, Если c самый большой общий делитель a а также b это означает a=z'c а также b=z''c тогда это Личность Безу формы

введите описание изображения здесь

с a=z' а также b=z'' и уравнение имеет бесконечное число решений. Таким образом, вместо метода пробного поиска вы можете проверить если c это наибольший общий делитель (GCD) из a а также b (в вашем случае это переводится на bx - dy = c - a)

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

введите описание изображения здесь

и ваш ответ:

a = k*x,
b = k*y,
c - a = k * gcd(a,b) для любого целого числа К.

(в качестве примечания: это относится и к любым другим Евклидов домен, то есть кольцо полинома & каждый евклидов домен уникальная область факторизации). Ты можешь использовать Итерационный метод чтобы найти эти решения:


Итерационный метод

По обычной алгебре расширения и группировки подобных терминов (обратитесь к последнему разделу статья в википедии упоминалось ранее), получается следующий алгоритм для итерационного метода:

  • 1 Примените евклидов алгоритм, и пусть qn (n начинается с 1) будет конечным списком частных в делении.
  • 2 Инициализируйте x0, x1 как 1, 0 и y0, y1 как 0,1 соответственно.
    • 2.1 Тогда для каждого i, пока определяется qi,
    • 2.2 Вычислить xi + 1 = xi − 1 — qixi
    • 2.3 Вычислить yi + 1 = yi − 1 — qiyi
    • 2.4 Повторите вышеупомянутое после увеличения i на 1.
  • 3 Ответы являются вторыми по последним из xn и yn.

псевдокод:

function extended_gcd(a, b)
x := 0    lastx := 1
y := 1    lasty := 0
while b ≠ 0
quotient := a div b
(a, b) := (b, a mod b)
(x, lastx) := (lastx - quotient*x, x)
(y, lasty) := (lasty - quotient*y, y)
return (lastx, lasty)

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

int gcd_iterative(int a, int b, int& x, int& y) {
int c;
std::vector<int> r, q, x_coeff, y_coeff;
x_coeff.push_back(1); y_coeff.push_back(0);
x_coeff.push_back(0); y_coeff.push_back(1);

if ( b == 0 ) return a;
while ( b != 0 ) {
c = b;
q.push_back(a/b);
r.push_back(b = a % b);
a = c;
x_coeff.push_back( *(x_coeff.end()-2) -(q.back())*x_coeff.back());
y_coeff.push_back( *(y_coeff.end()-2) -(q.back())*y_coeff.back());
}
if(r.size()==1) {
x = x_coeff.back();
y = y_coeff.back();
} else {
x = *(x_coeff.end()-2);
y = *(y_coeff.end()-2);
}
std::vector<int>::iterator it;
std::cout << "r: ";
for(it = r.begin(); it != r.end(); it++) { std::cout << *it << "," ; }
std::cout << "\nq: ";
for(it = q.begin(); it != q.end(); it++) { std::cout << *it << "," ; }
std::cout << "\nx: ";
for(it = x_coeff.begin(); it != x_coeff.end(); it++){ std::cout << *it<<",";}
std::cout << "\ny: ";
for(it = y_coeff.begin(); it != y_coeff.end(); it++){ std::cout << *it<<",";}
return a;
}

передавая ему пример из википедии для a = 120 а также b = 23 мы получаем:

int main(int argc, char** argv) {
// 120x + 23y = gcd(120,23)
int x_solution, y_solution;
int greatestCommonDivisor =  gcd_iterative(120, 23, x_solution, y_solution);
return 0;
}

r: 5,3,2,1,0,

q: 5,4,1,1,2,

х: 1,0,1, -4,5, -9,23,

у: 0,1, -5,21, -26,47, -120,

что соответствует приведенной таблице для этого примера:

введите описание изображения здесь

26

Другие решения

Других решений пока нет …

По вопросам рекламы [email protected]