Блог пользователя BekzhanKassenov

Автор BekzhanKassenov, 12 лет назад, По-русски

Здравствуй, сообщество Кодфорсес! В прошлом году я участвовал в олимпиаде, которую проводил МУИТ (Международная олимпиада по спортивному программированию среди учащихся 10-11 классов). Там попалась интересная задача, которую так никто и не решил.

Вот собственно и задача:

Даны 2 числа a и b и уравнение (a / x) + (b / y) = 1, где |a|, |b| <= 10^14. Нужно найти количество целочисленных решений этого уравнения.

Архив соревнования здесь. Каковы идеи решения?

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

»
12 лет назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

. Значит, если a·y делится на y - b, то для этого y существует x, и наоборот. Условие a·y делится на y - b равносильно тому, что a·y - a·(y - b) делится на y - b, т.е. a·b делится на y - b. Значит, ответ к задаче — это количество делителей числа a·b, которое можно найти, факторизовав a и b за .

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Да, то же самое, только надо еще не умножать и не делить на 0 и проверять отрицательные делители a*b.

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Я не совсем понял последний логический переход. Почему это так? Можно поподробней?

»
12 лет назад, # |
Rev. 8   Проголосовать: нравится 0 Проголосовать: не нравится

Рассматриваем случай a!=0 и b!=0, иначе решений бесконечно много, например: x=a и любой целый y при b=0.

Собственно если выразить X через Y, то получим X=a*y / (y-b). Разделим числитель и знаменатель дроби на y, получим: a/(1-b/y), откуда следует что a делится на (1-b/y) и b делится на y <=> y — делитель b. Положительные делители b мы можем перебрать за О(sqrt(b)), параллельно с их проверкой проверяем отрицательные значения. Таким образом мы найдем все решения вида c + z = 1, где c=a/x, z=b/y и c,z — целые.

Но могут быть еще и дробные варианты, т.е. a/x и b/y — не целые. Каждую из дробей a/x и b/y можно сократить на любой общий делитель a и b. Перебирая делители b мы также найдем общие делители с a, тогда получим все дробные уравнения вида p/x + q/y = 1, которые имеют до 2-ух интересующих нас решений:

пусть d — положительный общий делитель a и b.

  • для d получим p/x + q/y = 1, x=y=p+q — решение и x=-y=p-q — решение
  • для -d получим -p/x — q/y = 1, x=y=-p-q — решение и x=-y=-p+q — решение
  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Почему уравнение p/x + q/y = 1 имеет именно эти 4 решения?

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      вроде бы даже не 4, а 2. пусть d — положительный общий делитель a и b.

      • для d получим p/x + q/y = 1, x=y=p+q — решение и x=-y=p-q — решение
      • для -d получим -p/x — q/y = 1, x=y=-p-q — решение и x=-y=-p+q — решение

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

»
12 лет назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится
ay + bx = xy
(x-a)y = bx
y = bx/(x-a) = ba/(x-a) + b

пусть k — некоторый (возможно, отрицательный) делитель ab

x = a + k, 
y = ab/k + b

осталось выкинуть нули и проверить случай x = a решение

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    До какого значения надо перебирать к в вашем решении?

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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