c++ - 给定 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。

有谁知道执行此操作的更有效算法？谢谢你。

标签： c++algorithmmathoptimizationnumbers

Answer 1

单一查询

您可以使用以下算法通过计算以下丑数的数量n来获得 的位置：XX

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))需要重新创建缓存时运行。或者，您可以使用最大的预期数量预先创建缓存，以分摊创建缓存的成本。

避免溢出

对于接近 type 最大值的数字的查询，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;
}