bugdone's blog

By bugdone, history, 4 months ago,

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?

• +2

 » 4 months ago, # |   0 Auto comment: topic has been updated by bugdone (previous revision, new revision, compare).
 » 4 months ago, # |   +19 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$.
 » 4 months ago, # | ← Rev. 2 →   +1 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))
 » 4 months ago, # |   0 Just want to say that $2^{(k - 1) \times n} \not\equiv 2^{((k - 1) \times n)\ \%\ p}\ (mod\ p)$.