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

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

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

»
11 лет назад, скрыть # |
← 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;
}
»
11 лет назад, скрыть # |
← 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.