2^x * 3^y formasında olan ədədlərin sayı (Həll təhlili)

2^x * 3^y şəklində olan və 10^{18}-dən çox olmayan rəqəmlər o qədər də çox deyil. Onları yaradaraq $v$ massivində saxlayacağıq.

Müəyyən bir intervalda $[a,b]$ olan f(a, b) şəklində olan rəqəmlərin sayını aşağıdakı formada tapa bilərik:

Burada f(0, q) $q$-dən böyük olmayan 2^x * 3^y şəklində olan rəqəmlərin sayını ifadə edir. Bu sorğunun cavabını $v$ massivində ikili axtarış yolu ilə tapa bilərik.

Nümunə

$200$-dən çox olmayan 2^x * 3^y şəklində olan bütün rəqəmləri yaradacağıq.

$[1;10]$ intervalına $7$ rəqəm aiddir (mavi rənglə qeyd olunub).

$[100;200]$ intervalına $5$ rəqəm aiddir (yaşıl rənglə qeyd olunub).

$[10;20]$ intervalı üçün həllini tapaq:

Doğrudan da, $[10;20]$ intervalına $3$ axtarılan rəqəm aiddir:

Alqoritmin reallaşdırılması

MAX = 10^{18} sabitini və iş massivini $v$ elan edəcəyik.

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

preprocess funksiyası 10^{18}-dən çox olmayan bütün 2^x * 3^y şəklində olan rəqəmləri yaradır və onları $v$ massivində saxlayır. Hər bir x = 1, 2, 4, 8, ... üçün y = 1, 3, 9, 27, ... rəqəmlərini nəzərdən keçiririk, ta ki x * y < MAX olana qədər.

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

Sayıları $v$ massivində sıralağın.

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

Proqramın əsas hissəsi. 2^x * 3^y rəqəmləri massivini yaradırıq.

preprocess();

Sorğunu oxuyuruq — $[a,b]$ intervalı. Bu intervalda axtarılan rəqəmlərin sayı aşağıdakı formada hesablanır:

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