乐趣区

关于算法:欧拉项目-88题-数的乘积与和Productsum-number

jiezi

原文发表于这里，公式被渲染的很难看。

Problem 88

一个自然数 $N$ 如果能被至多两个自然数汇合 $\{a_1,a_2,\cdots,a_k\}$ 同时用乘积和和示意，即 $N=a_1+a_2+\cdots+a_k=a_1\times a_2\times\cdots\times a_k$，那么称为 Product-sum number。
比方 $6=1+2+3=1\times 2\times 3$。
给定一个固定大小 $k$，能够找到一个最小的 $N$ 是 Product-sum number。对于 $k=2,3,4,5,6$，最小 $N$ 如下
$$\begin{aligned}
k=2:&&&4=2\times 2=2+2\
k=3:&&&6=1+2+3=1\times 2\times 3\
k=4:&&&8=1\times 1\times 2\times 4=1+1+2+4\
k=5:&&&8=1\times 1\times 2\times 2\times 2=1+1+2+2+2\
k=6:&&&12=1\times 1\times 1\times 1\times 2\times 6=1+1+1+1+2+6
\end{aligned}$$
因而 $2\leq k\leq 6$，最小 Product-sum number$N$ 之和是 $4+6+8+12=30$，留神 8 只记录一次。
求 $2\leq k\leq 12000$ 时，最小 Product-sum number 的 $N$ 之和。

<!– more –>

先预计下数据量，下限是 12k，如果采纳暴力法，如果对于给定的 $k$ 可能线性工夫得出对应的最小的 $N$ 的话，复杂度也就 144M，对于 CPU 而言，是很小的量级，如果可能 $k\lg k$ 的工夫复杂度得出后果，也齐全是能够承受的。那么先依照暴力法思考下问题。
比方 $k=12,000$，$2^k$ 是一个很大很大的值，显然 12000 个数的和不可能有那么大的，所以不须要真的遍历 12000 个数，其实 $2^{15}=32768$ 就比 12000 大挺多的了，所以 $k$ 的低 15 个数字就能决定乘积与和是否相等了，残余的数字都是 1，很容易得出积与和。
既然只有 15 个数字就能决定的话，齐全不须要暴力求解了。
这里引入进位和加一的概念，把这 15 个数字当作 15 位，加一就是把最低为加一。进位呢？当乘积比和大的时候，就进一位，而后进位这个中央之后的数字放弃和前一位一样（这样做是为了不重不丢），这样乘积就会变小，比方 $2\times 2\times 90$ 进位失去 $2\times 3\times 3$，乘积从 360 降到 18。
如何判断从哪里进位呢？上述形容是说进位后的每一位和进位的数字放弃一样，所以从低位向高位扫描，两两比拟，如果雷同，阐明是从上次进位留下的后果，后续没有通过加一的步骤，无须再进位，第一次须要不同的中央，高位加一示意进位的操作，高位之后的数字天然放弃和高位一样的数字。
上面是形容进位的函数

private static bool Carry(int[] digits)
{for (int i = 0; i < digits.Length - 1; i++)
    {if (digits[i] != digits[i + 1])
        {digits[i + 1]++;
            for (int j = 0; j <= i; j++)
            {digits[j] = digits[i + 1];
            }

            return true;
        }
    }

    return false;
}

从最小值最低两位是 2 其余数字是 1 开始，加一，或者进位，直到进位也无奈无奈使得乘积再比和小（比方 $2,3,3,3,3$ 进位失去 $3,3,3,3,3$），或者无奈再进位（数字都一样），则完结整个过程。
这样失去一个汇合，每个元素是 15 个数字组成的汇合。那么对于每个 $k$ 对应的最小值 $N$ 都能用该汇合中某个元素示意，反过来想，这个汇合的每个元素，都决定了某个 $k$ 值对应的 $N$（这里不肯定是最小值）。通过过滤失去最小值是很容易。
当初问题是如果通过某个 15 个数字的汇合反推失去对应的 $k$。我计算失去这 15 个数字的乘积 p 与和 s，如果 $p\geq s$ 且 $p-s\leq 12000-15$（不要超出下限），令 $d=p-s$，差了一些，然而不多，那么 $k$ 比 15 大的话，求和时候后面有若干个一减少 $s$，使得 $p=s$，后面若干个是多少个？$d$ 个！所有这里的 $p$ 就是一个宽度为 $d+15$ 的Product-sum number。$p<s$ 的话，相当于后面的 1 多了，原理是一样的。
上面的代码反馈的就是上述的剖析。

// 定义 `ks`，用于保留各个宽度 k 对应的 `Product-sum number`
// 咱们从 k = 2 开始，所以第零个和第一个初始化成 0，前面初始化成最大值。int[] ks = new int[Max + 1];
ks[0] = 0;
ks[1] = 0;
for (int i = 2; i < ks.Length; i++)
{ks[i] = int.MaxValue;
}

// 0 开始是低位
int[] digits = new int[15] {2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1};

do
{
    // 计算差值，填充 diff+15 对应的 `Product-sum number`
    // 这里有一个大小的判断以存取最小值
    int product = digits.Aggregate(1, (a, b) => a * b);
    int sum = digits.Sum();
    int diff = product - sum;
    if (diff <= Max - 15 && diff >= -13 && ks > product)
    {ks = product;}

    // 每次迭代要么须要进位，要么进行加一操作
    // 如果无奈进位，迭代完结
    if (diff >= Max - 15)
    {bool ok = Carry(digits);
        if (!ok)
        {break;}
    }
    else
    {digits[0]++;
    }
} while (true);

有了一系列宽度 $k$ 对应的最小Product-sum number，去重求和失去最初的后果。

退出移动版