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

Math Problem
Автор MDantas, 12 лет назад, По-английски

Does anyone knows how to solve this problem:

Given two integers N,K ( 1 <= N,K <= 2^32 ) what's the answer for:

modulo (2^32)

edit: Sorry, I made a mistaken. The answer should be modulo 2^32, not 2^32 — 1 as I've written before.

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

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

Do you want a ready-made formula or algorithm?

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

Similar problem was in one of the Kharkov Winter Schools, but with much less constraints, K<=1000. You can solve problem with K<=1000, using some theory about Bernoulli number.

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

(2^32)-1 = 3*5*17*257*65537. With such a small rings, Chinese Remainder Theorem will make this problem almost trivial.

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

    Trivial ? What are you talking about ?

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

      n^k = 0 (mod m) for all n >= m (guess why) so you can just calculate answer for all given modules and then retrieve final answer using CRT.

      Solution for given prime module looks as follows:

      solve(int k, int mod) { res = 0 for (i = 1; i < mod; i++) res += pow(i, k); return res; }

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

        You are not rigth. 5^2 != 0(mod 4)
        But n^k = (n + m) ^ k(mod m). So
        solve(int n , int k, int mod)
        {
        res = 0;
        for (i = 1; i < mod; i++) res += pow(i, k);
        res *= n / mod;
        for (i = 1; i <= n % mod; i++) res += pow(i, k);
        return res % mod;
        }

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

          But MOD = 2^32 — 1, I can't just iterate over it. How can I compute the answer faster ?

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

            MOD = 3,5,17,257,65537. Then you need to use this to calculate the answer by mod 2^32-1 = 3*5*17*257*65537.

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

              Sorry, but I made a mistaken. The answer should be modulo 2^32. I don't think I can use Chinese Remainder Theorem with that modulo, or is it still possible ?

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

                if mod = 2^32 then you can't use Chinese Remainder Theorem. But I think it's possible to use Hensel's Lemma.

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

Look at http://community.topcoder.com/stat?c=problem_statement&pm=8725&rd=12169

they restricted K to 1-50, which doesn't really mean that it is impossible, but you know...

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

The specific modulus used here is important. Think about what happens if you write the sum as

[2*m]^k + [2*m+1]^k + [2*(m+1)]^k + [2*(m+1)+1]^k + ...

If k is large, clearly all even terms will disappear, as they will be divisible by 2^32. Then expand all terms of the form [2*a+1]^k using the binomial theorem, and you'll see most of the terms will be divisible by 2^32 too. You should be left with at most 31 terms to compute.

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

You can solve this problem with a recursive function :

solve(n, k) -> gives the answer for 1**k + 2**k + ... + n**k

The even terms together can be turned into a smaller instance of the original problem:

(2*1)**k + (2*2)**k + ... + (2*n/2)**k = (2**k) * (1**k + 2**k + ... + (n/2)**k)

S_even_terms = (2**k) * solve(n/2, k)

To manage the odd terms, as ffao`s said, you will need to calculate at most 31 terms of the binomial theorem.

the odd terms can be written as (2*a+1), for all values of a from 0 to (n-1)/2

The sum of the odd terms will be:

S_odd_terms = 1 + sum(i=0;i<=min(k, 31);i++) (2**i) * solve((n-1)/2, i)

The constant value 1 is there because a starts from 0 and the original problem starts from 1 So you add 1**k (the first even term) separately in the sum

It is enough to lead to a logarithmic behavior as the value of n is always dividing by two.

Do you know where I can test my code?

→ Ответить