题解：P5461 赦免战俘

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

思路

由于只有

0 1

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

0 1

转化为二进制。

下面看一下

n=3

时右上角的矩阵。

MARKDOWN

第一行

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

时右上角的矩阵。

MARKDOWN

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:

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

怎么递推呢？

我们希望前一个（即 $2^{2^n}-1$ ）的因数都能成为下一个数（ $2^{2^{n+1}}-1$ ）的因数。
我们希望前一个（即 $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^{2^{n+1}}-1=2^{t^2}-1=(2^t+1)(2^t-1)$ 。
若 $a|(2^t-1)$ ，显然有 $a|(2^t-1)(2^t+1)$ 。
若 $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 =

\begin{aligned} ‌&1340780792994259709957402499820\\&5846127479365820592393377723561\\&4437217640300735469768018742981\\&6690342769003185818648605085375\\&3882811946569946433649006084095 \end{aligned}

\approx 1.34\times10^{155}

。

如果你愿意加上高精度和快速幂也可以算，但不建议（应该没有人会这么做）。

时间复杂度

O(4^n\log n)

。

本题解只提供一种思路，当

n

过大时建议采用分治和递归去做。

大致实现方式：

分解 $2^{512} - 1$ ，得到全部质因数。
将因数转换为二进制。
逐位输出从 $1$ 到第 $2^n$ 个因数的二进制形式。

题解：P5461 赦免战俘

文章操作

思路

#update at 2025.09.15:

相关推荐

评论

题解：P5461 赦免战俘