可分数列｜数学归纳法

第四题 - 可分数列

题目链接跳转：点击跳转

题目很简单，但需要仔细想一会儿才行。这道题的解决思路就是 找规律！没错，就是找一下规律就好了。我们只需要关注如何将这 $4N + 2$ 个数列在去掉两个元素后可以被平均分成 $N$ 个等差数列。

通过手动模拟的方式，注意到我们只需要把这些数字竖着排列就可以解决问题。另每一列有四个元素，但其中有两列有五个元素（代表 $4N + 2$ 的 $+2$ 部分），共有 $N$ 列。例如数列 $[1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27]$。竖着排列之后就是这个样子的：

1 7 13 19 25
3 9 15 21 27
5 11 17 23

可以看到这些元素构成了三个等差数列，且两个等差数列的长度为 $5$。那么对于长度为 $4$ 的等差数列我们完全可以不用管，直接输出就好了。而对于这两个长度为 $5$ 的等差数列，我们考虑从这两个等差数列中各删除一个数字来构成新的等差数列。综合来看，我们发现删除元素 $3$ 和 $25$ 后，新的两个等差数列依旧满足题目限定的条件。

再多列举几个例子，发现规律也是相通的。那么因此我们可以得出结论，对于任意一个长度为 $4N + 2$ 的等差数列，只需要删除这个等差数列的第 $2$ 项和第 $4N + 1$ 项，剩下的 $4N$ 个元素一定可以组成 $N$ 个长度为 $4$ 的等差数列。

关于本题的更多信息，可以阅读 アイドル 老师的题解作为补充：链接跳转。

找到规律后代码就很好写了，本题的 AC 代码如下：

#include <iostream>
#include <algorithm>
#define int long long
using namespace std;

int n, x, d;

signed main(){
    cin >> n >> x >> d;
    if (n == 1){
        cout << -1 << endl;
        return 0;
    }
    cout << 2 << " " << 4 * n + 1 << endl;
    for (int i=0; i<n; i++){
        int t = x + i * d;
        if (i == 1) t += n * d;
        for (int j=0; j<4; j++)
            cout << t + j * n * d << " ";
        cout << endl;
    }
    return 0;
}