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.
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 164 |
| 1 | maomao90 | 164 |
| 3 | Um_nik | 163 |
| 4 | atcoder_official | 160 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 8 | Dominater069 | 154 |
| 8 | nor | 154 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 14.11.2024 08:00:54 (j2).
Десктопная версия, переключиться на мобильную.
При поддержке
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?