神仙构造。
因为余数相等不好构造，所以想到钦定这个余数为 \(1\)，比较直观的方法就是取出一些不相邻的格子，然后它们的权值为其相邻格子的 \(\text{lcm}+1\)。由于它们权值比较大，称其为大格子。
显然最多能取 \(\frac{n^2}{2}\) 个大格子（棋盘染色取同色即可），那么每一个剩下的小格子其实都被大格子包围了。所以我们不用考虑它们被其它数除的余数。
你首先会想到小格子全部放上不同的质数，但是这样的话质数个数是 \(O(n^2)\) 的，大概会填到 \(1655131=p_{1.25\times 10^5}\)。然后每个大格子是旁边 \(4\) 个质数的积 \(+1\)，但是还有权值限制，你可能会爆炸。
我们发现，在上述构造方法中，每个大格子是相邻 \(4\) 个质数的乘积左右。如果我们只用 \(O(n)\) 以内的质数，再平衡一下，大概率是不会爆炸的。所以我们考虑如何只使用 \(O(n)\) 个质数。
之所以之前的方法是 \(O(n^2)\) 的，是因为你给平面上的每个小格子都分配了一个质数。于是我们考虑某些小格子都共用一个质数（即有一个公共质因子）。不难发现给每条正/反对角线分别配 \(2n\) 个不同的质数，每个小格子取经过它的两条对角线上的质数的乘积，不难发现每个大格子的权值还是 \(4\) 个质数的乘积。
再平衡一下对角线上质数大小的分布就能过了。一开始我写的是给每个对角线随机一个质数，但是好像会炸时间。实际上直接贪心即可。