Here is a trick to calculate the summation related to floor function Sum{ floor((a+d*i)/m) | 0<=i<n}.

Let’s count in another way. Let g(k) be the number of i such that floor((a+d*i)/m)>=k,

then the summation would be Sum{ g(k) | 1<=k}. The second summation would be in the form

of Sum{floor( (a’+m*k)/d )+ constants | 1<=k}, so we can let m=m%d and the denominator decrease.

We can recursively apply the above transformation until the coefficient of variable i becomes 0.

The whole recursive procedure is just like that of Euclid’s algorithm for greatest common divisor,

so the time complexity is logarithmic.

Let’s count in another way. Let g(k) be the number of i such that floor((a+d*i)/m)>=k,

then the summation would be Sum{ g(k) | 1<=k}. The second summation would be in the form

of Sum{floor( (a’+m*k)/d )+ constants | 1<=k}, so we can let m=m%d and the denominator decrease.

We can recursively apply the above transformation until the coefficient of variable i becomes 0.

The whole recursive procedure is just like that of Euclid’s algorithm for greatest common divisor,

so the time complexity is logarithmic.

Advertisements