题解 | #杨辉三角的变形# 数学公式推导验证周期律

1. 首先，当 n == 1 || n == 2 时，易知不存在偶数项，输出 - 1

2. 当 n % 2 != 0 时，第一项为 1，第二项为 (n - 1)，(n - 1) % 2 == 0， 故可知奇数行的第二项一定为偶数；

3. 当 n % 2 == 0 时，第一项为 1，第二项为 (n - 1) 一定为奇数，经过证明可知第三项与第四项的奇偶性一定相反，证明过程如下：

   我们考虑当 n >= 3 时的第四项系数 a(n)。

   n == 3 时，$a\left(3\right)=(3-2)a(3)\; =\; (3\; -\; 2)$a(3)=(3−2) + $C_2^{2}C\_2^2$C22​

   n == 4 时，$a\left(4\right)=(4-2)a(4)\; =\; (4\; -\; 2)$a(4)=(4−2) + $C_3^{2}C\_3^2$C32​ + $a\left(3\right)a(3)$a(3)...

   则 $a\left(n\right)=1+2+...+(n-2)a(n)\; =\; 1\; +\; 2\; +\; ...\; +\; (n\; -\; 2)$a(n)=1+2+...+(n−2) + $C_2^{2}C\_2^2$C22​ + $C_3^{2}C\_3^2$C32​ + ... + $C_{n-1}^{2}C\_\{n-1\}^2$Cn−12​ = $C_2^{2}C\_2^2$C22​ + $C_3^{2}C\_3^2$C32​ + ... + $C_{n-2}^{2}C\_\{n-2\}^2$Cn−22​ + 2 * $C_{n-1}^{2}C\_\{n-1\}^2$Cn−12​, 其中 2 * $C_{n-1}^{2}C\_\{n-1\}^2$Cn−12​ 一定为偶数，当 (n - 2)为奇数且 n > 4 时，可知前面的部分可以分成偶数个 ($C_k^{2}C\_k^2$Ck2​ + $C_{k+1}^{2}C\_\{k+1\}^2$Ck+12​)对，每一对都为偶数，因此可知当 (n - 2)为奇数即 n 为奇数时，a(4) 一定为偶数。

   对于偶数行 (n >= 4)，考虑第四项与第三项系数之差。这个的差值与第 (n - 1)行的第四项系数与第一项系数之差相等，即为 a(n - 1) - 1。当 n 为奇数时，由上述可知奇数行的第四项系数 a(n) 为偶数，则 a(n) - 1 一定为奇数。 因此偶数行的第四项与第三项互为奇偶。 而第三项为 $C_n^{2}C\_n^2$Cn2​, 与第 (n + 2) 行的第三项作差，有 $C_{n+2}^{2}C\_\{n+2\}^2$Cn+22​ - $C_n^{2}C\_n^2$Cn2​ = 2 * n + 1 为奇数。因此相邻偶数行的第三项也互为奇偶。

   由此可知：

   若偶数行第 n 行第三项为奇数，则第 (n + 2) 行的第三项一定为偶数；

   若偶数行第 n 行第三项为偶数，则第 (n + 2) 行的第四项一定为偶数；

   因此得到了周期律，n == 4 时，第三项为偶数，可知n == 6 时第四项为偶数，剩下的类推，n 为 4 的倍数时一定为第三项，剩下的偶数项一定为第四项。

#include <iostream>

using namespace std;

int main() {
    int n;
    while (cin >> n) {
        if (n == 1 || n == 2) cout << -1 << endl;
        else if (n % 2 != 0) cout << 2 << endl;
        else if (n % 4 == 0) cout << 3 << endl;
		else cout << 4 << endl;
    }
    return 0;
}