Modulo Matrix

xht · 2023-09-27 01:40:51 · 题解

Modulo Matrix

题意

• 你要构造一个 n \times n 的矩阵 a，满足：
  • 所有 a_{i,j} 互不相同。
  • 对于任意两个相邻的数 x,y，\max(x,y) \bmod \min(x,y) 为定值。

题解

如下图构造：

其中黄格子是两个质数的乘积，白格子为周围黄格子的 \text{lcm} + 1。

代码

namespace shai {
    const int n = 1e6 + 7;
    int p[n], v[n], phi[n], miu[n];

    inline void init(int n) {
        v[1] = phi[1] = miu[1] = 1;
        for (int i = 2; i <= n; i++) {
            if (!v[i]) p[++p[0]] = v[i] = i, phi[i] = i - 1, miu[i] = -1;
            for (int j = 1; j <= p[0] && i * p[j] <= n && p[j] <= v[i]; j++)
                v[i*p[j]] = p[j],
                phi[i*p[j]] = phi[i] * (p[j] - 1 + (p[j] == v[i])),
                miu[i*p[j]] = p[j] == v[i] ? 0 : -miu[i];
        }
    }
}
using shai::p;

const int N = 507;
int n, a[N], b[N];

int main() {
    shai::init(1e4);
    rd(n);
    for (int i = 1; i <= n; i++) a[i] = p[i&1?i/2+1:n*2-i/2+1];
    for (int i = 1; i <= n; i++) b[i] = p[(i&1?n-i/2:n+i/2)+(n&1)];
    a[0] = a[n+1] = b[0] = b[n+1] = 1;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            print((i ^ j) & 1 ? 1ll * a[(i+j)/2] * a[(i+j)/2+1] * b[(n+i-j+(n&1))/2] * b[(n+i-j+(n&1))/2+1] + 1 : 1ll * a[(i+j)/2] * b[(n+i-j+(n&1))/2], " \n"[j==n]);
    return 0;
}