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

# | User | Rating |
---|---|---|

1 | MiFaFaOvO | 3681 |

2 | Um_nik | 3544 |

3 | maroonrk | 3431 |

4 | tourist | 3409 |

5 | apiadu | 3397 |

6 | 300iq | 3317 |

7 | ecnerwala | 3260 |

7 | Benq | 3260 |

9 | LHiC | 3229 |

10 | TLE | 3223 |

# | User | Contrib. |
---|---|---|

1 | Errichto | 193 |

2 | antontrygubO_o | 191 |

3 | vovuh | 178 |

4 | pikmike | 177 |

5 | tourist | 166 |

6 | Um_nik | 165 |

7 | McDic | 164 |

8 | ko_osaga | 163 |

9 | Radewoosh | 162 |

10 | Geothermal | 157 |

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

↑

↓

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/02/2020 01:01:26 (i2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Do you want a ready-made formula or algorithm?

You already can see a formula in the description )

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.

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

Actually you can find some formulas here, page-15-16

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

Trivial ? What are you talking about ?

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

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;

}

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

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.

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 ?

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

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

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.

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?