Please read the new rule regarding the restriction on the use of AI tools. ×

nilsilu95's blog

checking parity of n!/b iopc14
By nilsilu95, history, 9 years ago, In English

http://www.codechef.com/IOPC2014/problems/IOPC14A

What is the way to solve this problem? Most of solutions seems to check (n!mod (2*b))>=b or not ,whats the reason for this?

  • Vote: I like it
  • +6
  • Vote: I do not like it

Comments Comments (10)
| Write comment?
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

You can calc the power of 2 in n!(it's n/2+n/4+n/8+...) and power of 2 in b(just divide it by 2 while n%2=0) and compare this values

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    vintage_Vlad_Makeev your idea is wrong probably because it's integer division. For eg:

    a) 12 = 22 * 3 , 8 = 23, (12 / 8 = 1) % 2 = 1

    b) 20 = 22 * 5 , 8 = 23, (20 / 8 = 2) % 2 = 0

    But powers of 2 in (12, 8) and (20, 8) are same. You could find a similar case for factorials as well.

    → Reply
»
9 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Each student gets n! / b (integer division) oranges. If n!%(2b) is less than b, then it can be written as 2*k*b + r for some integer k and r < b. Then n!/b is equal to 2*k, so each student gets an even number of oranges. If n!%(2b) is >= b, then it can be written as 2*k*b + r where b <= r < 2*b, or 2*k*b + b + r', where r' = r — b, so 0 <= r' < b. Then, (2*k*b + b + r')/b = 2*k + 1, which is odd.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    one more doubt 


    long long mul( long long a, long long b, long long m ) {
  long long q = (long long)((long double)a * (long double)b / (long double)m);
  long long r = a * b - q * m;
  r %= m;
  if (r < 0) r += m;
  return r;
}

    The above code seems to be finding (a*b)%m ,but we can do directly right .then why coders do so?

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      Doing it directly could result in overflow.

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        but can (a%m)*(b%m)%m cause overflow?

        → Reply
        • »
          »
          »
          »
          »
          9 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Yes because they can both be up to m-1, and m can be up to 10^18

          → Reply
          • »
            »
            »
            »
            »
            »
            9 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            u r so fast in helping ,ty

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              9 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              one more doubt if i dont write long double it gives wa ~~~~~ (long long)((long double)a * (long double)b / (long double)m); ~~~~~

              and

              (long long)(a * b / m);

              whats difference

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                9 years ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                Long doubles are more precise than doubles, and long longs have a higher range of values than longs.

                → Reply