题解：P5461 赦免战俘

bayiran · 2025-06-29 09:10:24 · 题解

声明：这个想法是我在写题解时想到的，由于我很懒某些主观原因无法给出代码。

思路

由于只有 0 1，所以想到了二进制（虽然我不知道为什么要这样想），而且这题数据量很小，于是我决定把矩阵里的 0 1 转化为二进制。

下面看一下 n=3 时右上角的矩阵。

0 0 0 1 
0 0 1 1 
0 1 0 1 
1 1 1 1 

第一行 0001 = 2^0 = 1。

第二行 0011 = 2^0 + 2^1 = 3。

第三行 0101 = 2^0 + 2^2 = 5。

第四行 1111 = 2^0 + 2^1 + 2^2 + 2^3 = 15。

于是我们惊奇的发现：1,3,5,15 正好是 2^4-1 的全部因数！

接下来我手动打了一下 n=4 时右上角的矩阵。

0 0 0 0 0 0 0 1 
0 0 0 0 0 0 1 1 
0 0 0 0 0 1 0 1 
0 0 0 0 1 1 1 1 
0 0 0 1 0 0 0 1 
0 0 1 1 0 0 1 1 
0 1 0 1 0 1 0 1 
1 1 1 1 1 1 1 1 

这 8 行分别是：1,3,5,15,17,51,85,255，是 2^8-1 的全部因数。

所以，我们可以得出结论：对于 2^n \times 2^n 的矩阵，除左上的子矩阵外，剩余三个子矩阵每行为 2^{2^{n-1}} - 1 的全部因数的二进制形式。

证明以我目前的水平无法给出，希望有大佬补充证明。

update at 2025.09.15:

证明 by Marnie:

要证明的话，我们可以感觉到其中有一种递推的模式（正解也是递归，递归递推就是正反方向的区别），自然容易想到数学归纳法（一种递推证明的方法）。

怎么递推呢？

1. 我们希望前一个（即 2^{2^n}-1）的因数都能成为下一个数（2^{2^{n+1}}-1）的因数。

2. 我们希望前一个（即 2^{2^n}-1）的因数，左移2^n位后加上自己得到的数都是下一个数（2^{2^{n+1}}-1）的因数。

（比如 0001 变成 00010001, 0011 变成 00110011）。

二进制下左移 x 位就是乘以 2^x，也就是这个操作相当于把 a 变成 (2^{2^n}+1)a。

于是容易写出证明：

令 t=2^n，有：

2. 若 a|(2^t-1)，显然有 a|(2^t-1)(2^t+1)。
3. 若 a|(2^t-1)，显然有 (2^t+1)a|(2^t-1)(2^t+1)。

这样，递推的两个条件都满足。也就是当该结论对于 n=k 成立时，能推出 n=k+1 时也成立。从而对任意n该结论成立。

因为全都是可逆的,假设 a 是 (2^t-1)(2^t+1) 的因数，如果 a\div(2^t+1) 不整除 (2^t-1)，那么 a 不整除 (2^t-1)(2^t+1)，矛盾。

同理 a 是 (2^t-1)(2^t+1) 的因数，如果 a 不整除 (2^t-1)，那么 a 不整除 (2^t-1)(2^t+1)。

所以这些数一定是(2^2^n)-1的全部因数。

还有，当 n=10 时，2^{2^{n-1}} - 1 = 2^{512} - 1 =