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

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

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
  • Проголосовать: не нравится

»
10 лет назад, # |
  Проголосовать: нравится 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

→ Ответить
  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 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.

    → Ответить
»
10 лет назад, # |
  Проголосовать: нравится +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.

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

    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?

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

      Doing it directly could result in overflow.

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

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

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

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

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

            u r so fast in helping ,ty

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

              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

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

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

                → Ответить