nilsilu95's blog

checking parity of n!/b iopc14
By nilsilu95, history, 11 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?
»
11 years ago, hide # |
 
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
  • »
    »
    11 years ago, hide # ^ |
     
    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
»
11 years ago, hide # |
 
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
  • »
    »
    11 years ago, hide # ^ |
     
    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