algorithm - 整数距离

Question

As a single operation between two positive integers we understand multiplying one of the numbers by some prime number or dividing it by such (provided it can be divided by this prime number without the remainder). The distance between a and b denoted as d(a,b) is a minimal amount of operations needed to transform number a into number b. For example, d(69,42)=3.

Keep in mind that our function d indeed has characteristics of the distance - for any positive ints a, b and c we get:

a) d(a,a)==0

b) d(a,b)==d(b,a)

c) the inequality of a triangle d(a,b)+d(b,c)>=d(a,c) is fulfilled.

You'll be given a sequence of positive ints a_1, a_2,...,a_n. For every a_i of them output such a_j (j!=i) that d(a_i, a_j) is as low as possible. For example, the sequence of length 6: {1,2,3,4,5,6} should output {2,1,1,2,1,2}.

这对我来说真的很难。我认为有用的是:

a) 如果 a_i 是质数，我们不能做任何小于 a_i 的事情(除非它是 1)所以唯一允许的操作是乘法。因此，如果我们的集合中有 1，则对于每个质数，d(this_number, 1) 都是最小的。

b) 同样，对于 1 d(1, any_prime_number) 是最低的。

c) 对于一个非素数，我们检查我们的集合中是否有它的任何因子或它的因子的乘积

不过，这就是我所能推断的全部。最糟糕的是，我知道运行这样的算法并检查所有可能性需要很长时间……你能帮我解决一下吗？应该怎么做？

Answer 1

事实上，您可以将任何数字 N 表示为 2^n1 * 3^n2 * 5^n3 * 7^n4 * ...(大多数 n 为零)。

通过这种方式，您可以在数字 N 和无限序列 (n1, n2, n3, ...) 之间建立对应关系。

请注意，您的操作只是恰好在适当序列的一个位置上加或减 1。

设N和M为两个数，它们的序列为(n1, n2, n3, ...) 和(m1, m2, m3, ...)。 两个数字之间的距离确实就是|n1 - m1|。 + |n2 - m2| + ...

因此，为了找出最接近的数字，您需要计算所有输入数字的序列(这只是将它们分解为素数)。有了这个分解，计算就简单了。

---

编辑:
事实上，您不需要素因数的确切位置:您只需要知道每个素因数的指数即可。

---

编辑:
这是将数字转换为链表示的简单过程:

#include <map>

typedef std::map<unsigned int, unsigned int> ChainRepresentation;
// maps prime factor -> exponent, default exponent is of course 0

void convertToListRepresentation(int n, ChainRepresentation& r)
{
    // find a divisor
    int d = 2;

    while (n > 1)
    {
        for (; n % d; d++)
        {
            if (n/d < d) // n is prime
            {
                r[n]++;
                return;
            }
        }

        r[d]++;
        n /= d;
    }
}

---

编辑:
...和距离代码:

#include <set>

unsigned int chainDistance(ChainRepresentation& c1, ChainRepresentation& c2)
{
    if (&c1 == &c2)
        return 0; // protect from modification done by [] during self-comparison

    int result = 0;

    std::set<unsigned int> visited;
    for (ChainRepresentation::const_iterator it = c1.begin(); it != c1.end(); ++it)
    {
        unsigned int factor = it->first;
        unsigned int exponent = it->second;
        unsigned int exponent2 = c2[factor];
        unsigned int expabsdiff = (exponent > exponent2) ?
                       exponent - exponent2 : exponent2 - exponent;
        result += expabsdiff;
        visited.insert(factor);
    }

    for (ChainRepresentation::const_iterator it = c2.begin(); it != c2.end(); ++it)
    {
        unsigned int factor = it->first;
        if (visited.find(factor) != visited.end())
            continue;
        unsigned int exponent2 = it->second;
        // unsigned int exponent = 0;
        result += exponent2;
    }

    return result;
}