题目描述

给定一个长度为 $n$ 的正整数序列 $a_1, a_2, \cdots, a_n$，我们称区间 $[l, r]$（$1 \le l \le r \le n$）为一个$\textit{可整除区间}$，如果存在一个整数 $d$ 满足 $l \le d \le r$，并且对所有 $l \le i \le r$，$a_i$ 都能被 $a_d$ 整除。我们称整个序列为$\textit{可整除序列}$，如果对于所有 $1 \le l \le r \le n$，区间 $[l, r]$ 都是可整除区间。

现给定另一个长度为 $n$ 的序列 $b_1, b_2, \cdots, b_n$ 和一个整数 $k$，请找出所有 $1 \le x \le k$ 的整数 $x$，使得序列 $b_1 + x, b_2 + x, \cdots, b_n + x$ 是可整除序列。由于这样的整数可能很多，你只需要输出这样的 $x$ 的个数以及所有这样的 $x$ 的和。

输入格式

有多组测试数据。输入的第一行包含一个整数 $T$（$1 \le T \le 500$），表示测试数据组数。对于每组测试数据：

第一行包含两个整数 $n$ 和 $k$（$1 \le n \le 5 \times 10^4$，$1 \le k \le 10^9$）。

第二行包含 $n$ 个整数 $b_1, b_2, \cdots, b_n$（$1 \le b_i \le 10^9$）。

保证所有测试数据中 $n$ 的总和不超过 $5 \times 10^4$。

输出格式

对于每组测试数据，输出一行两个整数，用空格分隔，第一个数表示满足条件的 $x$ 的个数，第二个数表示所有满足条件的 $x$ 的和。

3
5 10
7 79 1 7 1
2 1000000000
1 2
1 100
1000000000

3 8
0 0
100 5050

提示

对于第一个样例测试数据，$x = 1$、$x = 2$ 和 $x = 5$ 是合法的。

对于第三个样例测试数据，所有的 $1 \le x \le 100$ 都是合法的。

由 ChatGPT 5 翻译