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

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

Просьба объяснить как сделать такую операцию : требуется найти (t^(ak)-1)/(t^a-1) по некоторому простому модулю (t- некоторая константа) Помогите пожалуйста разобраться, либо ссылочку, где можно почитать Просто я раскладывал в ряд t^(a(k-i)) где 1<=i<=k, но работает долго

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

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

Если ta ≠ 1 (mod p) (где p — модуль), то можно быстрым возведением в степень посчитать числитель и знаменатель дроби, им же найти обратный к знаменателю (пользуясь теоремой Ферма/Эйлера: ap - 2·a = 1 (mod p) и перемножить.

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

То, что выше описал Егор, не будет работать, если t не взаимно просто с p. Однако можно решить эту задачу и в таком случае, не пользуясь никакими делениями. Если не ошибаюсь, это была задача на одном из первых раундов последних SNWS.

.

Заметим, что если k чётно, то . Иначе можно посчитать просто: f(k) = ta·f(k - 1) + 1. За логарифмическое число шагов таким образом мы вычислим требуемую сумму.

В текущей версии решение работает за O(log2k) (на каждом шаге может понадобиться вызывать быстрое возведение в степень). Но можно аккуратно написать и просто пересчитывать выражение в скобках mdash; тогда сложность выйдет вообще O(logk).

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

    Вот почему плохо сильно править комментарии :D

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

      А, модуль-то простой. На том раунде не было условия, что модуль простой — тогда если нам не повезло и t не взаимно просто с p, то подобное заключение не спасает и нужно шагать, удваивая количество слагаемых в этой сумме, как я описал выше.

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

      OMG )