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

zorro_'s blog

(2^(2^n))%mod
By zorro_, 8 years ago, In English

Easy Money problem from HackerEarth Collegiate Cup Second Elimination round simplified to compute (2^(2^n))-1 with modulus 1e9+7.

To compute (2^(2^n))%mod, where mod = 1e9+7 and 1≤ n ≤10^18
author solution:
ans = power(2, n, mod -1)
ans = power(2, ans, mod)

Can someone please explain why mod -1 is taken ?

  • Vote: I like it
  • +21
  • Vote: I do not like it

Comments Comments (6)
| Write comment?
»
8 years ago, # |
  Vote: I like it +6 Vote: I do not like it

This is because by Fermat's Little Theorem, ap - 1 ≡ 1(modp). Thus, we reduce the exponent modulo p - 1 = 109 + 6.

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

I added a detailed explanation describing how to do it in the UPDATE section of the editorial, please take a look: https://www.hackerearth.com/hackerearth-collegiate-cup-second-elimination/algorithm/easy-money/editorial/

→ Reply