bugdone's blog

Doubt in Modular Arithmetic
By bugdone, history, 3 years ago, In English

Today in 1557C - Moamen and XOR I wanted to compute $$${(2^{k-1})}^{n}$$$. But instead of writing binpow(binpow(2, k — 1), n), I simplified it to $$$2^{(k-1)*n}$$$ and wrote binpow(2, mul(k — 1, n)) and failed to pass pretest 2.

Why are not the two equivalent?

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

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by bugdone (previous revision, new revision, compare).

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

I guess your mul() function looks like this: ll mul(ll x, ll y){ return x * y % mod; }

You can't take modulo $$$MOD$$$ in the exponent. You could take modulo $$$\phi({MOD})$$$ in the exponent, but not $$$MOD$$$.

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

if mul(n,k-1) is multiplication modulo some prime $$$p$$$ (that is, $$$10^9+7$$$ in the problem), then it is incorrect to say that

$$$a^{(b*c)} mod \ p = a^{((b*c) mod \ p)} mod \ p$$$

By little Ferma theorem, for prime p and any 0 < a < p, a^(p-1)=1, so what you needed actually is binpow(2, n*(k — 1) mod (p-1))

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Just want to say that $$$2^{(k - 1) \times n} \not\equiv 2^{((k - 1) \times n)\ \%\ p}\ (mod\ p)$$$.

→ Reply