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

Issue with large value
Автор _doomboo_, история, 11 месяцев назад, По-английски

I was solving this problem with a combinatoric based approach. So I compute binomial coefficient using Fermat Little Th. and modular inverse. I have correct values for N up to 34, then my code starts giving wrong values. I belive the approach is correct but there is some issue I cant figure out related to modulo, modular inverse or powmod function. Can anybody help me understanding why my code fails? CODE

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

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

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

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

Your C(n, k) function should be:

Spoiler
→ Ответить
  • »
    »
    11 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    it doesnt work anyway. I tried also approach with pascal triangle to compute nCk but I get the exact same issue: everything is fine for N up to 34, then it starts failing... it's so weird

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

Nobody able to help? :(

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

Please help

→ Ответить
»
11 месяцев назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

I might be wrong, but the 70'th line (ll half = nCk(n, n/2, mod)/2;) might mess your calculations up, maybe that nCk returns an odd number but you divide it by 2. I suggest using *inverse(2, mod). I haven't verified the code logic so I cannot say if the approach is correct or not. Hope this helps.

→ Ответить