构造喵喵题收录

Elegant Square

here
构造 n*n 的矩阵使每行与每列元素的乘积相等。要求不能出现重复元素，且每个数不能含有平方因子（不然 \(n\) 阶幻方秒了）。
考虑两组不交质数 \(a_i\) 和 \(b_i\)，取 \(ans_{i,j}=a_{(i+j)\bmod n}\times b_{(i-j)\bmod n}\)。显然此时行与列的乘积相等。若 \(n\) 为奇数显然 \((i,j)\) 与 \(((i+j)\bmod n,(i-j)\bmod n)\) 存在双射。
\(n\) 为偶数时需要增加一组质数 \(c_i\)。设 \(n=2m\)，则冲突只可能是 \((i,j)\) 与 \((i+m, (j+m) \bmod n)\) 形式。即需要将 \(\le m\) 和 \(>m\) 的数区分开。构造 \(c_{(2i+j+ \lfloor \frac{2i}{n} \rfloor)\bmod n}\) 即可。code