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

checking parity of n!/b iopc14
Автор nilsilu95, история, 11 лет назад, По-английски

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?

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

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

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

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

    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.

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

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.

→ Ответить