Pattern（差分循环模式）

版权信息

SAPO 2018 Round 2（南非计算机奥林匹克） © Original Problem Source: Programming Contest Archive / Educational Use Only

题目描述

从数字 2 开始，使用公差 3，可以得到数列：

如果从 2 开始，交替使用公差 3 和 -2，则可以得到：

（即：+3，-2，+3，-2，如此循环）

现在给定一个数列的前若干项，你需要：

👉 找到一个最短的“公差序列”（按顺序循环使用），使得从首项开始，可以生成整个数列。

输入格式

• 第一行：一个整数 $n$
• 第二行：$n$ 个整数，表示数列

输出格式

• 输出一组整数（空格分隔），表示最短的公差序列

样例

样例 1

输入：
5
2 5 8 11 14

输出：
3

样例 2

输入：
6
2 5 3 6 4 7

输出：
3 -2

样例 3

输入：
12
3 1 2 5 3 4 7 5 6 9 7 8

输出：
-2 1 3

说明（重要）

• 3 -2 3 -2 虽然也能生成序列，但不是最短
• -2 3 无法生成该序列

👉 必须输出最短循环节

测试数据

a)
8
1 5 9 13 17 21 25 29

b)
12
5 2 9 6 13 10 17 14 21 18 25 22

c)
11
10 13 15 18 14 19 22 24 27 23 28

d)
25
4 10 7 5 11 8 6 12 9 7 13 10 9 15 12 10 16 13 11 17 14 12 18 15 14