Учитывая X, определите n, где X - n-ое уродливое число

Question

"Уродливые числа - это числа, единственными простыми множителями которых являются 2, 3 или 5. последовательность 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15,… показывает первые 11 безобразно номера. По соглашению, 1 включено. "

Учитывая число X, определите порядок X в этой последовательности. Пример: X = 12, выход: 10.

Я сделал алгоритм грубой силы, который работает в O (XlogX):

long long cnt = 0;
for(long long i = 1; i<X; i++)
{
  long long tmp = i;
  while(tmp % 2 == 0) tmp/=2;
  while(tmp % 3 == 0) tmp/=3;
  while(tmp % 5 == 0) tmp/=5;
  if(tmp == 1) cnt ++;
}
cout << cnt+1 << endl;

Однако X может быть 1e18 и может быть 10 ^ 5 запросов, каждый запрос дает нам номер X.

Кто-нибудь знает более эффективный алгоритм для выполнения этой операции? Спасибо.

Answer 1

Одиночный запрос

Вы можете получить позицию n из X, посчитав количество уродливых чисел ниже X, используя следующий алгоритм:

int get_position(long long X)
{
    int n = 0;
    for(long long n2=1; n2<=X; n2*=2)
        for(long long n3=n2; n3<=X; n3*=3)
            for(long long n5=n3; n5<=X; n5*=5)
                ++n;
    return n;
}

Алгоритм перебирает все комбинации из 2, 3 и 5 кратных и работает в O(n), где n~log(X)³.

Несколько запросов

Если вы хотите повторить операцию несколько раз, вы можете сохранить таблицу для выполнения двоичного поиска:

struct ugly_numbers
{
    std::vector<long long> numbers{1};

    int get_position(long long X)
    {
        if(X>numbers.back())
        {
            std::set<long long> number_set;
            for(long long n2=1; n2<=X; n2*=2)
                for(long long n3=n2; n3<=X; n3*=3)
                    for(long long n5=n3; n5<=X; n5*=5)
                        number_set.insert(n5);
            numbers.assign(number_set.begin(), number_set.end());
        }
        auto value_it = std::upper_bound(numbers.begin(),numbers.end(),X);
        return (int)std::distance(numbers.begin(),value_it);
    }
};

Этот алгоритм запускается в O(log(n)), когда число является частью кэша, и в O(n*log(n)) когда кеш нужно пересоздавать.Кроме того, вы можете заранее создать кэш, используя наибольшее ожидаемое число, чтобы амортизировать стоимость создания кеша.

Предотвращение переполнения

Для запросов чисел, близких к максимальному значениютипа long long могут возникнуть ошибки переполнения и бесконечные циклы.Чтобы избежать этого, используйте следующий код (и используйте аналогичную логику с амортизированной версией):

int get_position(long long X)
{
    int n=0;
    long long max_n2 = std::min(X,std::numeric_limits<long long>::max() / 2);
    long long max_n3 = std::min(X,std::numeric_limits<long long>::max() / 3);
    long long max_n5 = std::min(X,std::numeric_limits<long long>::max() / 5);
    for(long long n2=1; n2<=max_n2; n2*=2)
        for(long long n3=n2; n3<=max_n3; n3*=3)
            for(long long n5=n3; n5<=max_n5; n5*=5)
                ++n;
    return n;
}