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

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

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

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

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

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

→ Ответить
»
13 лет назад, скрыть # |
← Rev. 8  
Проголосовать: нравится +6 Проголосовать: не нравится

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

.

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

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

→ Ответить