I don't know how to calc A%B+2A%B+3A%B....+KA%B effieciently....
(not (A%B+2A%B...+KA%B) % B..)
is there any math skills?? or nice algo??
any hints? thx
(not (A%B+2A%B...+KA%B) % B..)
is there any math skills?? or nice algo??
any hints? thx
COCI ALADIN. I need help..
I think you can use a little math...
You have (1A + 2A + 3A + 4A + 5A) % B actually because ( A + 2A ) % B = A % B + 2A % B
so in this case we have 15A % B, which is fast to calculate... I dont know if I understood you...
You have (1A + 2A + 3A + 4A + 5A) % B actually because ( A + 2A ) % B = A % B + 2A % B
so in this case we have 15A % B, which is fast to calculate... I dont know if I understood you...
(k*(k+1)/2)*A%B
This should do the trick,mate.
This should do the trick,mate.
i wouldn't say so.. you have to look at the sum in terms of integer division. a%b = a-[a/b]*b, 2a%b = 2a-[2a/b]*b ... you can take out the a's and sum them normally, then you are left with -b*( sum{ 1 <= x <= n of [xa/b] }. there's an euclidean-like algo for computing that sum
Well.... What I meant is (A%B)+(2*A%B)+(3*A%B)+...+(K*A%B)
not
(A%B+2A%B+...+KA%B) % B..
not
(A%B+2A%B+...+KA%B) % B..
um, i didn't even see the %b thing, and my post ignores that. as i said, you have to compute the sum of form ceil(a/b) + ceil(2a/b) + ... + ceil(na/b), from there it's easy to convert into mods
he needs the exact sum of mods... not the sum of mods mod b... so your formula is wrong :)
But.... it seems still hard to calc [a/b] + [2a/b] + ...+ [ka/b].. ><
Ok, I just can't be arsed to even go as far to try to figure out what you exactly want, but this is a formula I devised a while ago to get a sum of numbers from 1 to k :
(k*(k+1)/2
So if you want to calculate a/b+2a/b+3a/b...+ka/b, it can be done like this :
since a/b+2a/b+3a/b+...+k*a/b = (a+2a+3a+..+k*a)/b = sum of numbers [1..k]*a/b= ((k*(k+1)/2)*a)/b = ((k*(k+1))/2)*a/b
(k*(k+1)/2
So if you want to calculate a/b+2a/b+3a/b...+ka/b, it can be done like this :
since a/b+2a/b+3a/b+...+k*a/b = (a+2a+3a+..+k*a)/b = sum of numbers [1..k]*a/b= ((k*(k+1)/2)*a)/b = ((k*(k+1))/2)*a/b
well not exactly.. you need integer division here :) you can't extract the b out in integer division XD
anyways, here are some hints on how you can compute this sum... it's obviously defined by three values a, b, n => ( n summands, of form [ax/b]... ). now, if a > b, you can say a = qb + r, in the fractions you have qxa+[rx/b], you can sum the qxa's easily. now you have r instead of a, but the length doesn't change. the next part is most easily understood if we jump into some geometry. you've got a line defined as y = (a/b)x, and you have to count the integer points inside the triangle defined by the line, up to some x = n ( but not the points on the x-axis ). you can see that if you take the reciprocal slope, you get another line. this can be interpreted as a 'rotated' triangle, and you can calculate its lower side easily ( i'm writing this without consulting with a pen and paper so there are probably some mistakes :/, the side should be n*a/b ), now you have ( b, a, n*a/b )
and in the end, let's say you get a = 0 somewhere... the answer is obviously 0. you can implement it recursively, and as a drops down exponentially every second step, your running time is logarithmic...
anyways, here are some hints on how you can compute this sum... it's obviously defined by three values a, b, n => ( n summands, of form [ax/b]... ). now, if a > b, you can say a = qb + r, in the fractions you have qxa+[rx/b], you can sum the qxa's easily. now you have r instead of a, but the length doesn't change. the next part is most easily understood if we jump into some geometry. you've got a line defined as y = (a/b)x, and you have to count the integer points inside the triangle defined by the line, up to some x = n ( but not the points on the x-axis ). you can see that if you take the reciprocal slope, you get another line. this can be interpreted as a 'rotated' triangle, and you can calculate its lower side easily ( i'm writing this without consulting with a pen and paper so there are probably some mistakes :/, the side should be n*a/b ), now you have ( b, a, n*a/b )
and in the end, let's say you get a = 0 somewhere... the answer is obviously 0. you can implement it recursively, and as a drops down exponentially every second step, your running time is logarithmic...
ah.... I found the same formula in a topcoder single round match!!
SRM 410 Div1000!
and many thanks for your help~
SRM 410 Div1000!
and many thanks for your help~