Bit Diving in Divisors: An Optimization for Competitive Programmers

Efficiently Counting Divisors: Optimizing the Time Complexity

When we need to count the divisors of a number, a brute-force approach would involve checking all numbers from 1 to n to see if they divide n evenly. However, this method has a time complexity of O(n) , which can be inefficient for large numbers, such as 10^12. So, how can we optimize this?

Observing Patterns in Divisors

If you think about the divisors of a number, a pattern emerges. Consider the example of the number 100:

Divisors of 100 : ( 1, 2, 4, 5, 10, 20, 25, 50, 100 )

Notice that divisors come in pairs: - ( 1 times 100 ) - ( 2 times 50 ) - ( 4 times 25 ) - ( 5 times 20 ) - ( 10 times 10 )

Here’s the key insight: For divisors of 100, after you reach the square root of the number (in this case, 10), the remaining divisors are just the pair of the ones you’ve already found. For example, ( 100 / 4 = 25 ) and \( 100 / 25 = 4 ). Therefore, you can simply store one of them and move on.

Key Insight

By iterating only up to the square root of the number ( n ), we can drastically reduce the number of iterations. This method ensures that we only need to check potential divisors up to ( sqrt{n} ). If ( n ) is divisible by some number ( i ), we count both ( i ) and ( n / i ), unless they are the same (which happens when ( i ) equals ( sqrt{n} ).

Optimized Code

Here’s how we can implement this efficient approach in C++:

// ll is long long in C++ for large integers
ll countDivisors(ll n) {

 ll count = 0;

 for (ll i = 1; i * i <= n; i++) {
 if (n % i == 0) { // If i divides n evenly
 count++; // Count i as a divisor
// If i is not equal to n / i, count the other divisor as well
   if (i * i != n)  count++;
  }
 }
return count; // Return the total number of divisors
}        

Why Does This Work?

By looping up to ( sqrt{n} ), we ensure that we only check each divisor pair once. For example, for ( n = 100 ), we only check divisors up to 10. The divisors greater than 10 (like 20, 25, 50, 100) are automatically handled because of the pairing property.

- When ( i = 1 ), ( 100 / 1 = 100 ) (both divisors are counted). - When ( i = 2 ), ( 100 / 2 = 50 ) (both divisors are counted). - And so on, until ( i = 10 ), where we only count one divisor because ( 10 times 10 = 100 ).

This optimization reduces the number of iterations from O(n) to ( O(sqrt{n}), making it much more efficient for large values of ( n ).

Special Case: Perfect Squares

As noted earlier, when ( i ) equals ( sqrt{n} ) (like when ( n = 100 ) and ( i = 10 ), we only count the divisor once, as both divisors are the same. This is handled in the condition:

if (i * i != n) {
 count++; // Count only one divisor if i == n / i
}        

Conclusion

Using the square root method to count divisors significantly reduces the computational complexity, especially for large numbers. Instead of checking up to ( n ), we only check up to ( sqrt{n} ), which results in a huge performance gain. This is a great example of how understanding the properties of numbers can lead to more efficient algorithms.

If you’re dealing with large numbers and need to count divisors efficiently, this approach is the way to go!