Как решить линейные диофантовы уравнения в программировании? - PullRequest
Новая
       44

Как решить линейные диофантовы уравнения в программировании?

3 голосов
/ 03 апреля 2012

Я читал о линейных диофантовых уравнениях, таких как ax+by=c, которые называются диофантовыми уравнениями и дают целочисленное решение, только если gcd(a,b) divides c.

Эти уравнения имеют большое значение в соревнованиях по программированию. Я просто искал в интернете, когда натолкнулся на эту проблему. Я думаю, это вариация диофантовых уравнений.

Проблема:

У меня есть два человека, Человек X и Человек Y, оба стоят в середине веревки. Человек Х может прыгнуть на А или В на левую или правую часть за один ход. Человек Y может прыгнуть либо на C, либо на D влево или вправо за один ход. Теперь мне дали номер K, и я должен найти нет. из возможных положений на веревке в диапазоне [-K, K], так что оба человека могут достичь этого положения, используя свои соответствующие фильмы любое количество раз. (A, B, C, D и K приведены под вопросом).

Мое решение:

Я думаю, что проблема может быть решена математически с помощью диофантовых уравнений.

Я могу сформировать уравнение для Лица X, например A x_1 + B y_1 = C_1 where C_1 belongs to [-K,K], и аналогично для Лица Y, например C x_2 + D y_2 = C_2 where C_2 belongs to [-K,K].

Теперь мое пространство поиска сводится к тому, чтобы просто найти количество возможных значений, для которых C_1 и C_2 одинаковы. Это будет мой ответ на эту проблему.

Чтобы найти эти значения, я просто нахожу gcd(A,B) и gcd(C,D), а затем беру lcm из этих двух gcd , чтобы получить LCM(gcd(A,B),gcd(C,D)), а затем просто вычисление количества точек в диапазоне [1, K], кратных этому lcm .

Мой окончательный ответ будет 2*no_of_multiples in [1,K] + 1.

Я пытался использовать ту же технику в моем коде C ++, но он не работает (неправильный ответ).

Это мой код: http://pastebin.com/XURQzymA

Мой вопрос: кто-нибудь может сказать мне, правильно ли я использую диофантовы уравнения?

Если да, может кто-нибудь сказать мне возможные случаи, когда моя логика не работает.

Это некоторые тестовые примеры, которые были приведены на сайте с формулировкой проблемы.

A B C D K даны как входные данные в той же последовательности, и соответствующий выходной сигнал указан в следующей строке:

2 4 3 6 7

3

1 2 4 5 1

3

10 12 3 9 16

5

Это ссылка на исходную проблему. Я написал оригинальный вопрос на простом языке. Возможно, вам будет трудно, но если вы хотите, вы можете проверить это:

http://www.codechef.com/APRIL12/problems/DUMPLING/

Пожалуйста, дайте мне несколько тестов, чтобы я мог понять, где я делаю не так?

Заранее спасибо.

Ответы [ 2 ]

13 голосов
/ 03 апреля 2012

Решение линейных диофантовых уравнений

ax + by = c и gcd(a, b) делит c.

  1. Разделите a, b и c на gcd (a, b).
  2. Теперь gcd (a, b) == 1
  3. Найти решение aU + bV = 1, используя Расширенный евклидов алгоритм
  4. Умножьте уравнение на c. Теперь у вас есть (Uc) + b (Vc) = c
  5. Вы нашли решение x = U*c и y = V * c
0 голосов
/ 03 апреля 2012

Проблема в том, что входные значения являются 64-битными (до 10 ^ 18), поэтому LCM может иметь размер до 128 бит, поэтому l может переполниться. Поскольку k является 64-разрядным, переполнение l указывает k = 0 (поэтому ответ равен 1). Вы должны проверить этот случай.

Например: 

unsigned long long l=g1/g; // cannot overflow
unsigned long long res;
if ((l * g2) / g2 != l)
{
    // overflow case - l*g2 is very large, so k/(l*g2) is 0
    res = 0;
}
else
{
    l *= g2;
    res = k / l;
}
...