CODEWITHSUNDEEP
c++algorithmtime-complexity
Jason Hank
Jason Hank

Reputation: 21

How to get the sum of divisors in a given range efficiently?

I'm trying to find the sum of all divisors of c in a give range a, b a <= b.

I've tried to loop from a to b and sum all divisors of c, but this seems inefficient, because the absolute difference between a and b can be 10^9. Is there a way that reduces the time complexity of this approach? 

int a, b, c;
cin >> a >> b >> c;
long long sum = 0;
for (int i = a; i <= b; i++) {
    if (i % c == 0) {
       ans += i;
    }
}
cout << sum << endl;

Upvotes: 0

Views: 965

Answers (2)

selbie
selbie

Reputation: 104514

Identify all the prime numbers that are divisors of c first. That will leave you with a list of numbers [w,x,y,z…]. Then keep a hash table set of all multiples of integers in this list that are also divisors.

int a, b, c;
cin >> a >> b >> c;
long long sum = 0;

std::vector<int> all_prime_factors = // Get all prime factors of c
std::unordered_set<int> factorSet;
for (int primefactor : all_prime_factors)
{
    int factor = primefactor;
    while (factor <= b)
    {
        if (factor % c == 0)
            factorSet.insert(factor);
        factor += primefactor;
    }
}

for (int x : factorSet)
{
    sum += x;
}

cout << sum << endl;

Upvotes: 2

Michael Veksler
Michael Veksler

Reputation: 8475

Note: the question is unclear whether we need to sum divisors (in the description) or divisible integers (in the code sample). The answer sums up divisible items.

This is simple.

  • Find from, the smallest value such that from % c == 0 && from >= a
  • Find to, the largest value such that to % c == 0 && to <= b

.

 int n = (to - from) / c + 1;
 return n * (to + from) / 2;

Return to - from + c. Take care of boundary conditions when to could overflow your type and from can underflow.

To find from do something like:

if (c < 0) c *= -1;  // works unless c == MIN_INT
if (a % c == 0)
   from = a;
else if (a >= 0)
   from = (a / c * c) + c
else 
   from = a / c * c;

Similarly for to, but accounting for the fact that we need to round down, and not up.

Also, need to handle the case of a > b separately.

EDIT

Here is the complete code with no loops, recursion, or containers. It runs in O(1):

int a, b, c;
std::cin >> a >> b >> c;
if (!std::cin) {
   std::cout << "input error\n";
   return 0;
}

if (c < 0) c*= -1;
const int from = [a,c] {

   // no rounding needed
   if (a % c == 0) return a;

   // division rounds down to zero
   if (a > 0) return (1 + a / c) * c;

   // division rounds up to zero
   return a / c * c;
}();

const int to = [b,c] {

   // no rounding needed
   if (b % c == 0) return b;

   // division rounds down to zero
   if (b > 0) return (b / c) * c;

   // division rounds up to zero
   return (b / c - 1) * c;
}();

int64_t sum = 0;
if (from <= to)
{
 const int n = (to - from) / c + 1;
 sum = n * (to + from) / 2;
}
std::cout << sum << '\n';

Upvotes: 3

Related Questions