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

Doubt in Modular Arithmetic
Автор bugdone, история, 3 года назад, По-английски

Today in 1557C - Moamen и 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
  • Проголосовать: не нравится

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

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

→ Ответить
»
3 года назад, # |
  Проголосовать: нравится +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$$$.

→ Ответить
»
3 года назад, # |
← 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))

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

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

→ Ответить