← 返回题目列表

Codeforces · 1269/B

B. 模相等

中文机器翻译题面 查看原题

给定一个正整数 $$$m$$$ 和两个整数序列:$$$a=[a_1, a_2, \ldots, a_n]$$$ 和 $$$b=[b_1, b_2, \ldots, b_n]$$$。这两个序列的长度都是$$$n$$$。

排列是 $$$n$$$ 不同正整数的序列,从 $$$1$$$ 到 $$$n$$$。例如,这些序列是排列:$$$[1]$$$、$$$[1,2]$$$、$$$[2,1]$$$、$$$[6,7,3,4,1,2,5]$$$。这些不是:$$$[0]$$$、$$$[1,1]$$$、$$$[2,3]$$$。

您需要找到非负整数 $$$x$$$,并将 $$$a_i$$$ 的所有元素增加 $$$x$$$,以 $$$m$$$ 为模(即您想要将 $$$a_i$$$ 更改为 $$$(a_i + x) \bmod m$$$),因此可以将 $$$a$$$ 的元素重新排列为使其等于$$$b$$$,其中你需要找到尽可能小的$$$x$$$。

换句话说,你需要找到最小的非负整数 $$$x$$$,为此可以找到一些排列 $$$p=[p_1, p_2, \ldots, p_n]$$$,这样对于所有 $$$1 \leq i \leq n$$$, $$$(a_i + x) \bmod m = b_{p_i}$$$,其中 $$$y \bmod m$$$ — $$$y$$$ 除以 $$$m$$$ 的余数。

例如,如果$$$m=3$$$,$$$a = [0, 0, 2, 1],b = [2, 0, 1, 1]$$$,您可以选择$$$x=1$$$,$$$a$$$将等于$$$[1, 1, 0, 2]$$$,您可以重新排列它以使其相等$$$[2, 0, 1, 1]$$$,等于$$$b$$$。

输入

第一行包含两个整数 $$$n,m$$$ ($$$1 \leq n \leq 2000, 1 \leq m \leq 10^9$$$):数组中元素的数量和 $$$m$$$。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i < m$$$)。

第三行包含 $$$n$$$ 整数 $$$b_1, b_2, \ldots, b_n$$$ ($$$0 \leq b_i < m$$$)。

保证存在一些非负整数 $$$x$$$,这样就可以找到一些排列 $$$p_1, p_2, \ldots, p_n$$$ 使得 $$$(a_i + x) \bmod m = b_{p_i}$$$。

输出

打印一个整数,最小的非负整数 $$$x$$$,这样就可以找到一些排列 $$$p_1, p_2, \ldots, p_n$$$ 使得 $$$(a_i + x) \bmod m = b_{p_i}$$$ 对于所有 $$$1 \leq i \leq n$$$ 。

示例

输入 #1

4 3
0 0 2 1
2 0 1 1

输出 #1

1

输入 #2

3 2
0 0 0
1 1 1

输出 #2

1

输入 #3

5 10
0 0 0 1 2
2 1 0 0 0

输出 #3

0