Count the integers of the form 2^x * 3^y (Editorial)

There are not so many numbers of the form 2^x * 3^y that do not exceed 10^{18}. We can generate them and store them in an array $v$.

The number of such values f(a, b) in the range $[a,b]$ can be found using the formula:

Here, f(0, q) represents the number of values of the form 2^x * 3^y that do not exceed $q$. This can be efficiently found using binary search on the array $v$.

Example

Let’s generate all numbers of the form 2^x * 3^y that do not exceed $200$.

The interval $[1;10]$ contains $7$ numbers (highlighted in blue).

The interval $[100;200]$ contains $5$ numbers (highlighted in green).

Let's find the solution for the interval $[10;20]$:

Indeed, the interval $[10;20]$ contains $3$ numbers of the desired form:

Algorithm implementation

Let's define the constant MAX = 10^{18} and an array $v$.

#define MAX 1000000000000000000LL
vector<long long> v;

The function preprocess generates all numbers of the form 2^x * 3^y that do not exceed 10^{18} and stores them in the array $v$. For each value of x = 1, 2, 4, 8, ... iterate over numbers y = 1, 3, 9, 27, ... until x * y < MAX.

void preprocess()
{
  long long x = 1, y = 1;
  while (x < MAX)
  {
    while (x * y < MAX)
    {
      v.push_back(x * y);
      y *= 3;
    }
    x *= 2;
    y = 1;
  }

Sort the numbers in the array $v$.

  sort(v.begin(), v.end());
}

The main part of the program. Generate the array of numbers of the form 2^x * 3^y.

preprocess();

Read a query — the interval $[a,b]$. The number of desired integers in this interval is computed using the formula:

while (scanf("%lld %lld", &a, &b) == 2)
{
  res = upper_bound(v.begin(), v.end(), b) – upper_bound(v.begin(), v.end(), a - 1);
  printf("%lld\n", res);
}