Блог пользователя Hesham.Elkhatib

Wilson's Theorem
Автор Hesham.Elkhatib, 11 лет назад, По-английски

I Want to know how wilson theorem can be used to efficiently calculate nCr % P where P is prime

and how it can help to solve this Problem

also it will be appreciated to mention some of its applications :)

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

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

You don't do this using Wilson. Wilson is about , while your factorials are n!, (n - r)!, r!, none of which are in any way related to p.

If p > n, we know that r! and (n - r)! are coprime to p, therefore

by Fermat's little theorem. If $n$ is small enough, you can pre-compute all factorials up to n and the rest is just fast modular exponentiation.

Also, nCr is not a good notation. Try {n \choose r } in : .

Hope this helps in some way.

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

    I think that the exponent in formula should be p — 2, not p — 1.

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

    Well, there's some thing. I think the author may think about the case that n is very large (n > (1LL << 63)) and p is a int or long long type integer. I think there's something that wilson theorem can do. Let x = (n!) / ((n — r)! * r!), the answer.

    First thing to do, we should check if x == 0 by using Lp(n!)=∑[n/p^k] (k>=1). If x != 0, then since n is so large, the we should say n = k*p + b. Then

    n! = 1*2*...*(p — 2)*(p-1)*p*(p + 1)*(p+2)*...*(kp + 1)*(kp+2)*...(kp+b); = 1*2*...*(p -2)*(p — 1)*p*1*2*...*(p — 1)*2p*1*2...*(p — 1)*kp*1*2*...*b; = ((p — 1)!)^k*k!*b! MOD p;

    since k is also very large, we need recursion function to calculate that. b<p, so b! can be calculate in a short time, you can calculate all b! before everything starts. (n — r)! ans r! can be calculate in the same way. The use the quick_power to calculate the reverse. that's ((n-r)!*r!)^(p-2). That's it.:D

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

      Yes, that's another way. I don't see where you use Wilson's theorem, though. And it has the downside of using O(p) time and memory (the memory can be a bigger problem than the time here), which makes it applicable only for really small p.

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

        n! = 1*2*...*(p-2)*(p-1)*p*(p+1)*(p+2)*...*(kp+1)*(kp+2)*...(kp+b);

        = 1*2*...*(p-2)*(p-1)*p*1*2*...*(p-1)*2p*1*2...*(p-1)*kp*1*2*...*b;

        = ((p-1)!)^k*k!*b! MOD p;

        Using wilson theorem, we know (p-1)! = -1 MOD p; So this part ((p-1)!)^k will always be 1 or -1, depends on k.

        BTW the simplest way to calculate (n-r)!*r! will always cost O(p) time. Any faster way suggested, since you also need to calculate that in your method?

        And in the case that there're large numbers of inputs, I suggest pre-calculate all the b!, most of time we don't need to do that. :D

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

          Oh, ok. Still, Wilson just removes one line from the code, without improving its actual complexity :D

          I meant that p is mostly large (binomial coefficients usually appear as part of more complex combinatorial problems), so ways with O(n) precalculaton and time per query, or even with a 2D table of coefficients, are much more common. O(p) is almost just for this particular problem (for which tl;dr, I'm just looking at your post below :D).

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

        And I think my way just works fine for the problem the author asked as p < 1000 and n < 10^9 in the statement.

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

    I just ignore the factor p, since (n-r)!*r! and n! has the same number of factor p in the above case. BTW, recursion's depth won't be too deep(log(n)/log(p)). Otherwise n is so large that it can't be presented in the input. :D

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

    N in the problem can be up to 109 . P is only 103 , in the worst case. Lucas theorem is the only way to go.

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

What you need is not Wilson theorem, you need Lucas theorem :D

This problem is a straightforward problem on Lucas theorem.

Quoted from wikipedia: "

For non-negative integers m and n and a prime p, the following congruence relation holds:

where

and

are the base p expansions of m and n respectively. This uses the convention that = 0 if m < n.

"

Wikipedia Link

PS: Sorry for the many edits but seems like Codeforces has problems with long LaTex codes!!

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

    I find YQCMMD's solution above better, because it doesn't rely on Wikipedia (which is not exactly accessible in contests, so it's better not to get too used to it), but can be derived easily. Also, Lucas is overkill here. The simpler, the better.

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

really great, thanks all for your beneficial explanations :)

→ Ответить