整数距离

Question

作为两个正整数之间的单个运算,我们理解将其中一个数乘以某个素数或将其除以(假设它可以除以该素数而没有余数).表示为d(a,b)的a和b之间的距离是将数字a变换为数字b所需的最小操作量.例如,d(69,42)= 3.

请记住,我们的函数d确实具有距离的特征 - 对于任何正的整数a,b和c,我们得到:

a)d(a,a)== 0

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

c)满足三角形d(a,b)+ d(b,c)> = d(a,c)的不等式.

您将获得一系列正整数a_1,a_2,...,a_n.对于它们的每个a_i输出这样的a_j(j!= i),d(a_i,a_j)尽可能低.例如,长度为6:{1,2,3,4,5,6}的序列应输出{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;
}