MDantas's blog

Math Problem
By MDantas, 11 years ago, In English

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.

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

»
11 years ago, # |
← Rev. 2   Vote: I like it -13 Vote: I do not like it

Do you want a ready-made formula or algorithm?

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

    You already can see a formula in the description )

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

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.

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

    Sorry, but I got nothing with this. I'm not that good with this kind of problems.

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

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

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

    Trivial ? What are you talking about ?

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
      ← Rev. 2   Vote: I like it -17 Vote: I do not like it

      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; }

      → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
        ← Rev. 2   Vote: I like it +6 Vote: I do not like it

        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;
        }

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

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

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

            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.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              11 years ago, # ^ |
              ← Rev. 2   Vote: I like it 0 Vote: I do not like it

              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 ?

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                11 years ago, # ^ |
                ← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

                → Reply
»
11 years ago, # |
  Vote: I like it -8 Vote: I do not like it

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...

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

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.

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

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?

→ Reply