Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

Samsam's blog

A problem with mod
By Samsam, 11 years ago, In English

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 ?

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
11 years ago, # |
  Vote: I like it +8 Vote: I do not like it

(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

→ Reply
»
11 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Try the Modular Exponentiation Algorithm

→ Reply