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

Автор Dword, история, 6 лет назад, По-русски

Приветствую всех пользователей Codeforces. Возникла задача разделить один большой многочлен на другой. Решил использовать БПФ, но если при умножении многочленов все более-менее понятно, а именно перемножаются соответствующие значения ДПФ двух многочленов, то при делении возникают сложности, ведь значения ДПФ могут быть равны 0, а на 0 поделить, увы, не получится. Что же делать в такой ситуации? Буду также рад, если вы предложите какую-нибудь статью, которая разрешит мой вопрос (желательно на русском).

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

»
6 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

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

    Можете поподробнее об этом рассказать (или дайте что-нибудь почитать)?

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

      Подробнее гуглится по запросу тфкп особые точки

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

        Спасибо

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

        Хорошо. А что тогда делать, если какая-то комплексная точка будет являться полюсом? Многочлены нельзя будет разделить?

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

          Что вы ожидаете от частного многочленов? это просто будет дробь с двумя многочленами

»
6 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

Если в посте имелось в иду деление многочленов "в столбик" с остатком, то здесь можно почитать про то, как это делается с помощью БПФ.