CSP1263. 整除（divide）

• 时限: 1000 ms | 内存: 512 MB | 难度: 9

整除

题目描述

给定一个长度为 $n$ 的正整数序列 $a_1, a_2, \dots, a_n$，小 Z 称区间 $[l, r]$ （$1 \leq l \leq r \leq n$）为可整除区间，如果存在一个整数 $d\in [l,r]$，满足 $l \leq i \leq r$ 的所有 $i$ 都满足 $a_i$ 能被 $a_d$ 整除。

小 Z 称整个序列是可整除序列，如果对于所有的 $1 \leq l \leq r \leq n$，区间 $[l, r]$ 都是可整除区间。

现在，小 Z 给定另一个长度为 $n$ 的序列 $b_1, b_2, \dots, b_n$ 和一个整数 $k$。小 Z 构造了新序列 $b_1 + x, b_2 + x, \dots, b_n + x$，其中 $x$ 是一个整数。小 Z 给你的任务是找到所有的整数 $x$，使得 $1 \leq x \leq k$ 且构造的序列是一个可整除序列。

由于满足条件的整数 $x$ 的数量可能很大，你需要输出所有满足条件的整数 $x$ 的数量以及所有满足条件 $x$ 的和。

输入格式

从 divide.in 文件读入数据。

输入包含多个测试用例。

第一行包含一个整数 $T$，表示测试用例的数量。

对于每个测试用例：

• 第一行包含两个整数 $n$ 和 $k$。

• 第二行包含 $n$ 个整数 $b_1, b_2, \dots, b_n$。

输出格式

输出到 divide.out 文件。

对于每个测试用例，输出一行两个整数，表示满足条件的整数 $x$ 的数量以及所有满足条件 $x$ 的和。

样例 #1

样例输入 #1

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

Copy

样例输出 #1

3 8
0 0
100 5050

Copy

提示

【样例 1 解释】

第一个测试用例，$x = 1,2,5$ 是满足要求的。

第二个测试用例，没有一个 $x$ 满足要求的。

第三个测试用例，对于所有 $1\le x\le 100$ 都是满足要求的。

样例 2～ 4 都可以点击链接 divide_sample.zip 下载大样例压缩包，具体如下。

【样例 2】

见附件的 divide_sample2.in 与 divide_sample2.ans。

【样例 3】

见附件的 divide_sample3.in 与 divide_sample3.ans。

【样例 4】

见附件的 divide_sample4.in 与 divide_sample4.ans。

【数据范围】

对于 $20\%$ 的数据，满足 $1\le n,k \le 200$；

对于 $40\%$ 的数据，满足 $1\le n,k \le 2000$；

另有 $20\%$ 的数据，满足特殊性质 A;

对于 $100\%$ 的数据，满足 $1\le T\le 100,1\le n\le 10^5,1\le k \le 10^9,1\le b_i \le 10^9$， 保证所有测试用例中 $n$ 的总和不超过 $10^5$。

• 特殊性质 A: 序列 $b$ 中只有两种不同的数。