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

A problem with mod
Автор Samsam, 11 лет назад, По-английски

I have to get the sum of these terms (2 + 4 + 8 + 16 + ...... + 2^n) % (10^9 + 9). I know that the sum without the mod is given by the formula : 2*(1-2^n)/(1-2) = -2*(1-2^n) but I don't know how to get the sum mod 10^9 + 9. So please could you help me ?

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

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

(a+b) mod c == ((a mod c) + b) mod c. a * b mod c == ((a mod c) * b) mod c. now you can do it with fast exponentiation

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

Try the Modular Exponentiation Algorithm

→ Ответить