C++ 数论：计算 max(y = a_i * x+ b_i) <= k 的最快方法

Question

以下问题，当必须快速编写代码时：我有一个包含 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.

我已经有一个理论上可行的 "solution"，但是太慢了：

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，如果它们满足等式。如果其中一个失败，我必须继续，直到找到解决方案或 none (-1).

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

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

Answer 1

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

C++ 数论：计算 max(y = a_i * x+ b_i) <= k 的最快方法

C++ Number theory: Fastest way to compute max(y = a_i * x+ b_i) <= k

c++

performance

number-theory

integer-arithmetic

modular-arithmetic