思路
暴力解法是遍历清单 P 中的每个元素 x 和清单 Q 中的每个元素 y,计算 (x+y)(modK) 并找到最小值。这种方法的时间复杂度是 O(n×m)。考虑到 n 和 m 的最大值可达 100000,n×m 最大会达到 1010,这显然会超时。因此,我们需要一个更高效的算法。
我们可以优化查找过程。首先,(x+y)(modK) 的值等价于 ((x(modK))+(y(modK)))(modK)。所以我们可以先将两个清单中的所有元素都对 K 取模,这不会影响最终结果,但可以使数值处理更方便。
接下来,我们固定清单 P 中的一个元素 x,然后尝试在清单 Q 中寻找一个最优的 y 来与之配对。设 a=x(modK),我们希望找到一个 b=y(modK),使得 (a+b)(modK) 最小。
为了让 (a+b)(modK) 的值尽可能小,有两种主要情况: