Brainstorming Quiz, Day - 5 Solution

Answer: 13168380

Short Explanation:

The problem involves finding special numbers (ACES numbers) between two very large limits ll and rr. A number is considered ACES if it is divisible by the largest whole number less than or equal to its square root.

Approach:

1. Efficient Square Root Calculation: A binary search is used to find the square root for very large numbers without relying on direct mathematical operations.
2. Check Possible ACES Numbers: For each valid square root kk between the lower and upper bounds:
   • Numbers like k^2, k(k+1), and k(k+2) are checked to see if they are within the range [l,r][l, r].
   • These numbers are also checked to ensure divisibility by k.
3. Optimization: Instead of checking all numbers between ll and rr, only potential candidates derived from square roots are evaluated, making the process faster.

The program calculates and counts these numbers efficiently, even for very large inputs, and outputs the total count.

#include <bits/stdc++.h>
#define ll long long
using namespace std;

ll bs_sqrt(ll x) {
  ll left = 0, right = 2000000123;
  while (right > left) {
      ll mid = (left + right) / 2;
      if (mid * mid > x) right = mid;
      else left = mid + 1;
  }
  return left - 1;
}

int main(){
    ll l = 987642878877987659, r = 996386656794592367, ans = 0;
    ll left_sqrt = bs_sqrt(l);
    ll right_sqrt = bs_sqrt(r);
    ans = max(ans, right_sqrt - left_sqrt - 1) * 3;
    if (left_sqrt * left_sqrt >= l && left_sqrt * left_sqrt <= r) ans++;
    if ((left_sqrt * (left_sqrt + 1) >= l) && (left_sqrt * (left_sqrt + 1) <= r)) ans++;
    if ((left_sqrt * (left_sqrt + 2) >= l) && (left_sqrt * (left_sqrt + 2) <= r)) ans++;
    if (left_sqrt != right_sqrt) {
        if ((right_sqrt * right_sqrt >= l) && (right_sqrt * right_sqrt <= r)) ans++;
        if ((right_sqrt * (right_sqrt + 1) >= l) && (right_sqrt * (right_sqrt + 1) <= r)) ans++;
        if ((right_sqrt * (right_sqrt + 2) >= l) && (right_sqrt * (right_sqrt + 2) <= r)) ans++;
    }
    cout << ans << endl;
    return 0;
}