### MDantas's blog

By MDantas, 7 years ago, , 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. math, Comments (16)
 » 7 years ago, # | ← Rev. 2 →   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.
•  » » » 7 years ago, # ^ | ← Rev. 2 →   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 ?
•  » » » 7 years ago, # ^ | ← Rev. 2 →   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; }
•  » » » » 7 years ago, # ^ | ← Rev. 2 →   You are not rigth. 5^2 != 0(mod 4)But n^k = (n + m) ^ k(mod m). Sosolve(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.
•  » » » » » » » 7 years ago, # ^ | ← Rev. 2 →   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 ?
•  » » » » » » » » 7 years ago, # ^ | ← Rev. 2 →   if mod = 2^32 then you can't use Chinese Remainder Theorem. But I think it's possible to use Hensel's Lemma.
 » 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**kThe 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)/2The 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 sumIt 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?