题解 AT4378 【[AGC027D] Modulo Matrix】

· · 题解

如图所示，黑白染色后，每个黑色格子按照每个正 / 反斜对角线填上两个质数的乘积。

令 m=1，则白色格子上的数为相邻四个黑色格子上的数的 \mathrm{lcm} + 1。

稍微调整一下质数的顺序，就可以做到数不超过 10^{15} 了。

时间复杂度为 \mathcal O (n^2)，评测链接。