-4

以下问题，当必须编写快速代码时：我有一个包含 2 个整数 a_i 和 b_i 的列表，我必须计算等式：y = (a_i * x + b_i)，其中我只对 y 感兴趣，而不对X。所有 a_i 都是素数并且彼此不同。a_i = y / x，b_i = y % x。

y 有多个解，即使所有 a_i、b_i 对的 y 必须相同，因为 x 可以是任何整数。因此我们有一个上限 k 并且 y <= k。我想要尽可能高的 y（如果有解决方案）。最大值（y）。

简而言之：我想知道最大整数 y（如果存在的话），其中 y <= k 和给出的等式。x >= 1。

我已经有了一个理论上可行的“解决方案”，但这太慢了：

struct part {
unsigned int size, rest;
};

int solve(vector<part> &partions, int minK, int stepSize, int k) {
    int sol = 0;

    for (int i = k; i >= minK; i -= stepSize) {
        bool works = true;
        for (int j = 0; j < static_cast<int>(partions.size()); j++) {
            if ((i - partions[j].rest) % partions[j].size != 0) {
                works = false;
                break;
            }
        }
        if (works) return i;
    }



    return -1;
}

解释：minK 是 max(a_i + b_i)，因为我认为 y = a_i *1 + b_i 是一个方程的最小可能解，并且由于所有方程的 y 都是相同的，所以最大值是最好的下限。

stepSize 不是 1（为了使程序更快），而是 max(a_i)，正如我所想，max(a_i) 必须适合 y 和 y = a_i * x + b_i，因此 x 是整数值，stepSize 是 a_i，而 max(a_i) 是最好的，因为这样会减少循环运行的次数。

我现在用 stepSize 尝试从 k 到 minK 的所有 y，并测试所有对 a_i 和 b_i，如果它们满足方程。如果其中一个失败，我必须继续，直到找到解决方案或没有解决方案（-1）。

不幸的是，该算法太慢了（因为 a_i 和 b_i 可以达到 10^12），我想不出更多的优化。我已经在互联网上搜索了数论和算术，但找不到任何类似的东西。

你能帮我加快这段代码的速度，或者提示我到一些处理这个问题的网站吗？

4

1 回答 1

0

您可以一次满足一个 i，同时保留所有已满足的 i：step 是所有已满足的 a[i] 的 LCM（最初为 1）。y 是满足你已经做过的所有的最小值。关键概念是，任何满足所有 i 的 Y 都必须满足你已经完成的所有 Y，所以它必须是Y=y+n*step. 因此，对于每个 i，您可以直接计算y+n*stepmod a[i] 等于 b[i] 的最小 n（如果有）并设置y=y+n*step和 step=lcm(step,a[i])。如果没有这样的 n 或者如果新的 y 大于 k，则中止。一旦你通过了所有的 i，你就有了最小的 y，但你想要最大的 y 小于 k，这是一个微不足道的最终调整，因为它们相差多个步长。

于 2015-07-07T18:37:34.213 回答