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

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

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

Проблема :

У меня есть два человека, Человек X и Человек Y, оба стоят в середине веревки. Человек X может за один ход перепрыгивать юниты A или B влево или вправо. Человек Y может за один ход перепрыгивать юниты C или D влево или вправо. Теперь мне дали число К, и я должен найти ответ «нет». возможных положений на веревке в диапазоне [-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)), а затем просто вычисляю количество точек в range [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/

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

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


c++ algorithm algebra equation
person dark_shadow    schedule 03.04.2012    source источник
comment
Неужели обращение за помощью - это нарушение правил конкурса? Вы можете дождаться окончания конкурса?   -  person Nabb    schedule 03.04.2012
comment
Могу ли я ожидать какой-нибудь тестовый пример или хоть какой-то намек?   -  person dark_shadow    schedule 03.04.2012
comment
Чувак, твой код компилируется, запускается и дает правильные ответы на примеры. В чем именно проблема? PS: вашему алгоритму gcd не нужны аргументы по порядку; вы можете убрать 18 строк кода.   -  person Eddie Edwards    schedule 03.04.2012
comment
@EddieEdwards: Да, я знаю, что мой код отлично работает на примерах, но не знаю, почему я получаю неправильный ответ на codechef. Любая помощь будет принята с благодарностью.   -  person dark_shadow    schedule 03.04.2012
comment
Вы можете привести пример, когда это не удается?   -  person Eddie Edwards    schedule 03.04.2012
comment
Понятно - см. Ответ ниже - все дело в точной формулировке вопроса.   -  person Eddie Edwards    schedule 03.04.2012
comment
Вы не должны злоупотреблять сообществом, задавая проблемы из текущего конкурса (что противоречит правилам этого конкурса).   -  person Priyank Bhatnagar    schedule 03.04.2012
comment
Это не противоречит правилам этого конкурса. Посетите страницу правил здесь codechef.com/APRIL12.   -  person Eddie Edwards    schedule 03.04.2012
comment
@EddieEdwards, Пожалуйста, не обсуждайте стратегию, предложения или советы в комментариях во время живого конкурса. Публикация вопросов, разъясняющих формулировку проблемы, - это нормально. Да, конечно, обращение за помощью на любом другом веб-сайте кажется нормальным: |   -  person Priyank Bhatnagar    schedule 03.04.2012
comment
Ага, ну :) Он все равно решил проблему самостоятельно. Упущена небольшая деталь. И он, кажется, бесследно исчез, теперь у него есть исправление, так что, мальчик, я чувствую себя хорошо, что помог ему :)   -  person Eddie Edwards    schedule 03.04.2012

Ответы (2)


arrow_upward
13
arrow_downward

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

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. Теперь у вас есть a (Uc) + b (Vc) = c
  5. Вы нашли решение x = U*c и y = V * c
person Jarosław Gomułka    schedule 03.04.2012

arrow_upward
0
arrow_downward

Проблема в том, что входные значения 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;
}
person Eddie Edwards    schedule 03.04.2012
comment
Извините за поздний ответ, но, как вы сказали, я работал над проблемой. То, что вы указали, кажется правильным, поэтому я попытался решить проблему на Java с помощью BigInteger, но получил NZEC :( Я все еще работаю над этим и с нетерпением жду решения этой проблемы. - person dark_shadow; 03.04.2012
comment
Приведенное выше исправление делает это с вашим исходным кодом в нескольких строках. Вам просто нужно проверить переполнение (умножить, затем разделить, и если результат правильный, вы сделали не переполнения) и установить res = 0, если это произойдет. - person Eddie Edwards; 04.04.2012