Finding the sum of mod operations in the range

Question

if we have 2 numbers, say a and b , then how can we find the sum of b%i where i ranges from 1 to a ? One way is to iterate over all the values ​​from 1 to a, but is there an efficient method? (better than O (n)?) For example: if a = 4 and b = 5, then ans = 5% 1 + 5% 2 + 5% 3 + 5% 4 = 4 is required Thank you.

Answer 1

For i > b we have b % i == b , so that part of the sum is easily calculated in constant time ( (ab)*b if a >= b , 0 otherwise).

The part for i <= b remains calculated ( i == b gives 0, so it can be ignored). You can do this in steps O (sqrt (b))

• For i <= sqrt(b) calculate b % i and add to the sum
• For i > sqrt(b) , k = floor(b/i) , then b % i == b - k*i and k < sqrt(b) . So, for k = 1 to ceiling(sqrt(b))-1 , hi = floor(b/k) and lo = floor(b/(k+1)) . There are hi - lo numbers i such that k*i <= b < (k+1)*i , the sum b % i for them is sum_{ lo < i <= hi } (b - k*i) = (hi - lo)*b - k*(hi-lo)*(hi+lo+1)/2 .

If a <= sqrt(b) , only the first bullet is applied, stopping at a . If sqrt(b) < a < b , in the second pool, run from k = floor(b/a) to ceiling(sqrt(b))-1 and adjust the upper limit for the smallest k to a .

The total complexity is O (min (a, sqrt (b))).

Code (C):

 #include <stdlib.h> #include <stdio.h> #include <math.h> unsigned long long usqrt(unsigned long long n); unsigned long long modSum(unsigned long long a, unsigned long long b); int main(int argc, char *argv[]){ unsigned long long a, b; b = (argc > 1) ? strtoull(argv[argc-1],NULL,0) : 10000; a = (argc > 2) ? strtoull(argv[1],NULL,0) : b; printf("Sum of moduli %llu %% i for 1 <= i <= %llu: %llu\n",b,a,modSum(a,b)); return EXIT_SUCCESS; } unsigned long long usqrt(unsigned long long n){ unsigned long long r = (unsigned long long)sqrt(n); while(r*r > n) --r; while(r*(r+2) < n) ++r; return r; } unsigned long long modSum(unsigned long long a, unsigned long long b){ if (a < 2 || b == 0){ return 0; } unsigned long long sum = 0, i, l, u, r = usqrt(b); if (b < a){ sum += (ab)*b; } u = (a < r) ? a : r; for(i = 2; i <= u; ++i){ sum += b%i; } if (r < a){ u = (a < b) ? a : (b-1); i = b/u; l = b/(i+1); do{ sum += (ul)*b; sum -= i*(ul)*(u+l+1)/2; ++i; u = l; l = b/(i+1); }while(u > r); } return sum; }