algorithm - 为什么 DC3 不能在后缀数组中用作 DC2？

Question

我正在阅读有关 DC3 以构造后缀数组的论文。我想知道为什么DC3不能作为DC2应用，这样计算会更快？

Answer 1

对于每两个整数$a,b$，都有一个整数$c\in\{0,1,2}$使得$a+c$和$b+c$都不能被 整除$3$。

但是，对于整数$a=0,b=1$，对于每个整数$c$，要么$a+c$被 整除$2$，要么$b+c$被 整除$2$。

$2$可除性之间的这种差异$3$使得在算法中必须使用$3$ 而不是使用$2$。实际上，每个$k$大于或等于的整数都$3$有效（因此最好使用$3$）。