Кількість чисел виду 2^x * 3^y (Розбір)

Чисел виду 2^x * 3^y, які не перевищують 10^{18}, не так вже й багато. Згенеруємо їх і збережемо в масиві $v$.

Кількість шуканих чисел f(a, b) на відрізку $[a,b]$ можна знайти за формулою:

Тут f(0, q) позначає кількість чисел виду 2^x * 3^y, які не перевищують $q$. Відповідь на цей запит можна знайти за допомогою бінарного пошуку на масиві $v$.

Приклад

Згенеруємо всі числа виду 2^x * 3^y, які не перевищують $200$.

Відрізку $[1;10]$ належить $7$ чисел (виділені синім).

Відрізку $[100;200]$ належить $5$ чисел (виділені зеленим).

Знайдемо розв'язання для відрізка $[10;20]$:

Дійсно, відрізку $[10;20]$ належать $3$ числа шуканого виду:

Реалізація алгоритму

Оголосимо константу MAX = 10^{18} і робочий масив $v$.

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

Функція preprocess генерує всі числа виду 2^x * 3^y, які не перевищують 10^{18}, і зберігає їх у масиві $v$. Для кожного значення x = 1, 2, 4, 8, ... перебираємо числа y = 1, 3, 9, 27, ... доти, поки 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;
  }

Відсортуємо числа у масиві $v$.

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

Основна частина програми. Генеруємо масив чисел виду 2^x * 3^y.

preprocess();

Читаємо запит — відрізок $[a,b]$. Кількість шуканих чисел на цьому відрізку обчислюється за формулою:

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);
}