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

nCr % prime power

Автор Mid0, история, 9 лет назад, По-английски

i'm trying to calculate nCr mod prime power , i found this comment which is really helpful but the formula as i understand doesn't apply to some numbers and i don't know how it works , could anyone explain it in more details ?

  • Проголосовать: нравится
  • +6
  • Проголосовать: не нравится

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

Lucas's theorem. WIKI

int calc(int n, int k, int mod) {
  int res = 1;
  while (n || k) {
    res = (res * c[n % mod][k % mod]) % mod;
    n /= mod;
    k /= mod;
  }
  return res;
}
→ Ответить
  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    this works well for primes , but it doesn't work for prime power . for example try 28 choose 3 mod 27 it gives zero while the correct answer is nine .

    → Ответить
  • »
    »
    9 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Lucas' theorem stated that p must be a prime.
    The OP said he needed nCr modulo a prime power (pSomeNumber).

    I'm not sure whether Lucas' theorem still holds.

    → Ответить
»
9 лет назад, # |
← Rev. 2   Проголосовать: нравится +12 Проголосовать: не нравится

Once I've coded it in Python, maybe it'll help. (See nCk_mod_prime_power function)

Based on this paper by Andrew Granville.

→ Ответить